Сложность времени, чтобы найти первые N чисел, делимых только на 2, 3 и 5

Question

Проблема - В чем сложность найти первые N чисел, которые делятся только на 2, 3, 5?

Мои усилия

Код -

void printFirstNNumbers(int N) {

    int numbersFound = 0;

    // loop#1
    for(int cnt = 0; ; cnt++) {
        int currentNumber = cnt;

        // loop#2
        while(currentNumber != 1) {
            if(currenNumber%2 == 0) currentNumber /= 2;
            else if(currentNumber%3 == 0) currentNumber /= 3;
            else if(currentNumber%5 == 0) currentNumber /= 5;
            else break;
        }

        if(currentNumber == 1) {
            cout << currentNumber;
            numbersFound++;
            if(numbersFound == N) return;
        }
    }
}

Расчет сложности -

Сложность цикла № 2 - O( ln(i)), это происходит, когда каждый раз, когда число делится на 2, и, наконец, оно достигает 1.

Сложность цикла № 1 - O(T), где T - это число раз, которое он повторяет, чтобы получить первые N чисел.

Таким образом, сложность заключается в суммировании ln (i), где i = 2 к T.

C = summation of ln(i), where i = 2 to T.

2^C = 2*3*....T = factorial(T)

C = ln( factorial(T) )

where factorial(N) = sqrt(2*pie*N)* (N/e)^N

значит, факториал (N) прямо пропорционален (N)^(3N/2)

По приведенному выше уравнению,

C = ln ( (T)^(3T/2) ) = (3T/2) ln(T)

C = O(T ln(T) ).

Вопросы -

1. Можем ли мы представить T в терминах N?
2. Если да, то, пожалуйста, помогите мне преобразовать это.

Answer 1

Числа, которые вы пытаетесь найти, называются 5-гладкими. Одна из границ в статье Википедии предполагает, что O(log^3 T) 5-гладких чисел меньше T, поэтому, учитывая N, нам нужно установить T = 2^Omega(N^(1/3)).

Если вы пытаетесь перечислить 5-гладкие числа, алгоритм Дейкстры, вероятно, является подходящим способом, возвращая N чисел за O (N) времени.