Số xấu (Ugly Number) trong C++

Số xấu là số chỉ có các thừa số nguyên tố là 2, 3 hoặc 5. Từ 1 đến 15 có 11 số xấu: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15. Các số 7, 11, 13 không phải vì là số nguyên tố. 14 không phải vì có thừa số 7. Số xấu thứ 10 là 12.

Thuật toán

getUglyNumbers(n):
    uglyNum[0..n-1]
    i2=0, i3=0, i5=0
    next2mul=2, next3mul=3, next5mul=5
    next=1
    uglyNum[0]=1
    for i=1 đến n-1:
        next = min(next2mul, next3mul, next5mul)
        uglyNum[i] = next
        if next == next2mul: i2++; next2mul = uglyNum[i2]*2
        if next == next3mul: i3++; next3mul = uglyNum[i3]*3
        if next == next5mul: i5++; next5mul = uglyNum[i5]*5
    return next

Chương trình C++

#include <iostream> 
using namespace std; 

int min(int x, int y, int z) {
    if (x < y) return (x < z) ? x : z;
    else return (y < z) ? y : z;
}

int getUglyNum(int n) {
    int uglyNum[n];
    int i2 = 0, i3 = 0, i5 = 0;
    int next2mul = 2, next3mul = 3, next5mul = 5;
    int next = 1;
    uglyNum[0] = 1;
    
    for (int i = 1; i < n; i++) {
        next = min(next2mul, next3mul, next5mul);
        uglyNum[i] = next;
        if (next == next2mul) { i2++; next2mul = uglyNum[i2] * 2; }
        if (next == next3mul) { i3++; next3mul = uglyNum[i3] * 3; }
        if (next == next5mul) { i5++; next5mul = uglyNum[i5] * 5; }
    }
    return next;
}

int main() {
    int n;
    cout << "Enter term: "; cin >> n;
    cout << n << "th Ugly number is: " << getUglyNum(n) << endl;
}

Kết quả mẫu

Enter term: 10
10th Ugly number is: 12

Độ phức tạp

• Thời gian: O(n)
• Không gian: O(n) (có thể tối ưu O(1) nếu chỉ cần kết quả cuối)