Số có các thừa số nguyên tố chỉ là 2, 3 hoặc 5 được gọi là số Ugly (Ugly Number). Các số Ugly đầu tiên: 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, ...
Cho số N, tìm số Ugly thứ N trong dãy số Ugly.
Ví dụ
Input-1: N = 5
Output: 5
Giải thích: Số Ugly thứ 5 trong [1, 2, 3, 4, 5, 6, 8, 10, 12, 15] là 5.
Input-2: N = 7
Output: 8
Giải thích: Số Ugly thứ 7 là 8.
Phương pháp giải quyết
Cách đơn giản: Kiểm tra số có chia hết cho 2, 3, 5 không và đếm đến số thứ N.
- Nhập số N cần tìm số Ugly thứ N
- Hàm Boolean isUglyNumber(int n): Trả về true nếu n là số Ugly
- Hàm int nthUglyNumber(int n): Trả về số Ugly thứ n
Ví dụ mã Java
public class UglyN {
public static boolean isUglyNumber(int num) {
boolean x = true;
while (num != 1) {
if (num % 5 == 0) {
num /= 5;
} else if (num % 3 == 0) {
num /= 3;
} else if (num % 2 == 0) {
num /= 2;
} else {
x = false;
break;
}
}
return x;
}
public static int nthUglyNumber(int n) {
int i = 1;
int count = 1;
while (n > count) {
i++;
if (isUglyNumber(i)) {
count++;
}
}
return i;
}
public static void main(String[] args) {
int number = 100;
int no = nthUglyNumber(number);
System.out.println("The Ugly no. at position " + number + " is " + no);
}
}
Đầu ra
The Ugly no. at position 100 is 1536.