求k-素数的个数；
给定一个范围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)中完成吗？
- 我在这里使用动态规划吗？
回答 1
Stack Overflow用户
发布于 2013-07-17 17:06:35
您使用的算法称为埃拉托斯提尼筛。它是一种著名的求素数的算法。现在回答你的问题：
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))(B)能用O(n)做吗？
这很棘手。我想说的是，就所有实际目的而言，O(n log log n)算法将与任何O(n)算法一样好，因为log(log(n))增长非常慢。
现在，如果我的生活依赖于它，我会试着看看我是否能找到一种方法来生成直到n的所有数字，这样每个操作都生成一个唯一的数字，并告诉我它有多少唯一的素数除数。
2)我在这里使用动态规划吗？
维基百科对动态编程的定义是：
动态规划是将复杂问题分解为简单子问题的一种方法。
这一定义相当宽泛，因此不幸的是，它可供解释。我想说的是，这不是动态编程，因为您没有将您的问题分解为较小的、较小的子问题，并使用这些子问题的结果来找到最终的答案。
https://stackoverflow.com/questions/17694755
复制相似问题
腾讯云开发者
