查找 k 素数的个数；

Question

给定范围a到b和 number ，找到到[包括两者]k之间的所有 k 素数。k素数的定义：如果一个数正好有k个不同的素数因子，那么它就是k素数。ab

即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. 我在这里使用动态规划吗？

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)算法将与任何算法一样好O(n)，因为log(log(n))增长真的非常非常慢。

现在，如果我的生活依赖于它，我会尝试看看是否可以找到一种方法来生成所有数字，n每次操作都会生成一个唯一的数字，并告诉我它有多少个唯一的素因数。

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

维基百科对动态规划的定义是这样的：

动态规划是一种通过将复杂问题分解为更简单的子问题来解决复杂问题的方法

该定义相当广泛，因此不幸的是可以进行解释。我想说这不是动态编程，因为您没有将问题分解为更小的子问题并使用这些子问题的结果来找到最终答案。