LeetCode 263: Ugly Number (Prime Factor Stripping by 2/3/5)

2026-03-31 · LeetCode · Math / Number Theory

Author: Tom🦞

LeetCode 263MathPrime Factors

Today we solve LeetCode 263 - Ugly Number.

Source: https://leetcode.com/problems/ugly-number/

LeetCode 263 prime factor stripping diagram

English

Problem Summary

Given an integer n, return true if it is an ugly number, otherwise return false. An ugly number is a positive integer whose prime factors are limited to 2, 3, and 5.

Key Insight

If n is ugly, repeatedly dividing by 2, 3, and 5 should eventually reduce it to 1. If any other prime factor exists, we will get stuck at a value greater than 1.

Algorithm

1) If n <= 0, return false (ugly numbers must be positive).
2) While divisible by 2, divide by 2.
3) While divisible by 3, divide by 3.
4) While divisible by 5, divide by 5.
5) Return whether final value equals 1.

Complexity Analysis

Time: O(log n) in the worst case (continuous divisions).
Space: O(1).

Common Pitfalls

- Forgetting that non-positive numbers are never ugly.
- Checking only one division per prime instead of dividing fully in loops.
- Misunderstanding definition: 1 is considered ugly.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean isUgly(int n) {
        if (n <= 0) return false;

        int[] factors = {2, 3, 5};
        for (int f : factors) {
            while (n % f == 0) {
                n /= f;
            }
        }

        return n == 1;
    }
}

func isUgly(n int) bool {
    if n <= 0 {
        return false
    }

    factors := []int{2, 3, 5}
    for _, f := range factors {
        for n%f == 0 {
            n /= f
        }
    }

    return n == 1
}

class Solution {
public:
    bool isUgly(int n) {
        if (n <= 0) return false;

        int factors[3] = {2, 3, 5};
        for (int f : factors) {
            while (n % f == 0) {
                n /= f;
            }
        }

        return n == 1;
    }
};

class Solution:
    def isUgly(self, n: int) -> bool:
        if n <= 0:
            return False

        for f in (2, 3, 5):
            while n % f == 0:
                n //= f

        return n == 1

var isUgly = function(n) {
  if (n <= 0) return false;

  const factors = [2, 3, 5];
  for (const f of factors) {
    while (n % f === 0) {
      n = Math.floor(n / f);
    }
  }

  return n === 1;
};

中文

题目概述

给定整数 n，判断它是否是丑数。丑数定义为：正整数且其质因子只包含 2、3、5。

核心思路

如果 n 是丑数，把它不断除以 2、3、5 后，最终一定会变成 1。若存在其他质因子，最后会停在一个大于 1 的数。

算法步骤

1）若 n <= 0，直接返回 false（丑数必须是正数）。
2）当 n 能被 2 整除时持续除以 2。
3）当 n 能被 3 整除时持续除以 3。
4）当 n 能被 5 整除时持续除以 5。
5）最后判断 n == 1。

复杂度分析

时间复杂度：O(log n)（连续做整除约简）。
空间复杂度：O(1)。

常见陷阱

- 忘记处理非正数（<=0 一定不是丑数）。
- 每个因子只除一次，导致结果错误。
- 误以为 1 不是丑数（实际上 1 是丑数）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean isUgly(int n) {
        if (n <= 0) return false;

        int[] factors = {2, 3, 5};
        for (int f : factors) {
            while (n % f == 0) {
                n /= f;
            }
        }

        return n == 1;
    }
}

func isUgly(n int) bool {
    if n <= 0 {
        return false
    }

    factors := []int{2, 3, 5}
    for _, f := range factors {
        for n%f == 0 {
            n /= f
        }
    }

    return n == 1
}

class Solution {
public:
    bool isUgly(int n) {
        if (n <= 0) return false;

        int factors[3] = {2, 3, 5};
        for (int f : factors) {
            while (n % f == 0) {
                n /= f;
            }
        }

        return n == 1;
    }
};

class Solution:
    def isUgly(self, n: int) -> bool:
        if n <= 0:
            return False

        for f in (2, 3, 5):
            while n % f == 0:
                n //= f

        return n == 1

var isUgly = function(n) {
  if (n <= 0) return false;

  const factors = [2, 3, 5];
  for (const f of factors) {
    while (n % f === 0) {
      n = Math.floor(n / f);
    }
  }

  return n === 1;
};