c - 求 k 素数的个数；

Question

给定 a 到 b 的范围和数字 k ，找到 a 到 b [包括两者]之间的所有 k-素数。
k-素数的定义:如果一个数恰好有 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-质数。

问题:

这段代码的复杂度是多少，能在O(n)内完成吗？

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

Answer 1

您使用的算法称为 Sieve of Eratosthenes 。这是一个众所周知的寻找素数的算法。现在回答你的问题:

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) 。我们有一个 prime harmonic series ，它随着 ln(ln(b+1)) 渐近增长(参见 here )。

渐近上界是:

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

维基百科动态规划的定义说:

Dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems

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