时间复杂度，用于查找只能被 2、3 和 5 整除的前 N 个数字

Question

问题 - 找到只能被 2、3、5 整除的前 N 个数字的复杂性是多少？

我的努力

法典-

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. 我们可以用 N 来表示 T 吗？
2. 如果是，那么请帮助我转换它。

Answer 1

您要查找的数字称为 5-smooth。维基百科文章中的一个边界表明，有 O（log^3 T） 5 平滑数小于 T，所以给定 N，我们需要设置 T = 2^Omega（N^（1/3））。

如果你试图枚举 5 个平滑的数字，Dijkstra 的算法可能是要走的路，在 O（N） 时间内返回 N 个数字。