5

给定一个范围atob和 number ，找出所有介于to [包括两者]k之间的 k 素数。k-prime 的定义：一个数是 k-prime，如果它恰好有 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. 我在这里使用动态编程吗？
4

1 回答 1

2

您使用的算法被称为埃拉托色尼筛。这是一种众所周知的寻找素数的算法。现在回答你的问题：

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）我在这里使用动态编程吗？

维基百科对动态编程的定义说：

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

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

于 2013-07-17T17:06:35.797 回答