寻找k个素数的数量。

Question

给定区间 a 到 b，以及数字 k，找出在 a 到 b 范围内所有的 k-质数（包括 a 和 b）。 k-质数的定义：一个数恰好具有 k 个不同的质因数。 例如，当 a=4，b=10，k=2 时，答案为 2。因为数字 6 的质因数是 [2,3]，而数字 10 的质因数是 [2,5]。 以下是您需要翻译的内容：

#include<stdio.h>
#include<stdlib.h>
int main(){
    int numOfInp;
    scanf("%d",&numOfInp);
    int a,b,k;  
    scanf("%d %d %d",&a,&b,&k);
    int *arr;
    arr = (int*)calloc(b+1,sizeof(int));

    int i=2,j=2,count=0; 
    //Count is the count of distic k prim factors for a particular number
    while(i<=b){
        if(arr[i]==0){
            for(j=i;j<=b;j=j+i){
                arr[j]++;
            }
        }
        if(i>=a && arr[i]==k)
            count++;
        i++;
    }
    printf("%d\n",count);
    free(arr);

    return 0;
}

这个问题来自Codechef。

我的做法是创建一个大小为b的数组，对于从2开始的每个数字，我执行以下操作。

当数字为2时，检查arr[2]是否为0，如果是，则arr[2]++，arr[4]++，arr[6]++ ....以此类推。

当数字为3时，检查arr[2]是否为0，如果是，则arr[3]++，arr[6]++，arr[9]++ ....以此类推。

由于arr[4]不为零，因此跳过它。

最后，值arr[i]将给出答案，即arr[2]为1，因此2是1-质数，arr[6]为2，因此6是2-质数。

问题：

1. 这段代码的复杂度是多少，可以在O(n)内完成吗？
2. 我是否使用了动态编程？

- Kraken

---

这看起来像是一道作业题。你知道如何计算复杂度吗？ - levengli

@Kraken，代码中有一个内部循环的变量依赖于外部循环，这是O(n^2)复杂度的标志。此外，你的缩进可以更好一些，这样代码会更易读。 - Aseem Bansal

@AseemBansal 有没有办法将其降至O(n)？ - Kraken

@AseemBansal 实际上，你知道内部循环将运行多少次。您将为范围 [2,b] 中的每个质数运行一次。这些质数的数量不是 b 而是更小。该算法称为埃拉托色尼筛法。http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_complexity - cyon

除非我错了，否则这个程序的复杂度是 n*log(n)。 - levengli

Answer 1

您正在使用的算法称为埃拉托色尼筛法。这是一种用于寻找质数的知名算法。现在回答您的问题：

1a）此代码的复杂度是什么

您的代码复杂度为O(n log(log n))。

对于输入的a和b，您的代码复杂度为O(b log log b)。运行时间是因为您首先标记了b/2个数字，然后是b/3，再是b/5等等。因此，您的运行时间为b * (1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ... + 1/prime_closest_to_b)。我们在那里有一个质数调和级数，它的增长趋势渐近为ln(ln(b+1))（请参见此处）。

渐近地，上限为：

O(b * (1/2 + 1/3 + 1/5 + 1/7 +..)) = O(b) * O(log(log(b+1))) = O(b*log(log(b))

1b) 它能以 O(n) 的时间复杂度完成吗？

这有点棘手。我认为，对于所有实际目的而言，O(n log log n) 算法就已经足够好了，因为 log(log(n)) 增长非常非常缓慢。

现在，如果我的生命取决于它，我会尝试找到一种方法，在生成每个数字时都生成一个唯一的数，并告诉我它有多少个唯一的质因数。

2) 我在这里使用了动态规划吗？

维基百科上对动态规划的定义如下：

动态规划是一种通过将复杂问题分解成较小子问题来解决的方法。

这个定义很广泛，所以很遗憾它存在不同的解释。我认为这不是动态规划，因为你没有将问题分解为更小的子问题，并使用这些子问题的结果来找到最终答案。

- cyon