时间复杂度找到 n 个素数，尝试除以所有前面的素数

Question

问题：寻找 n 个素数。

#include<stdio.h>
#include<stdlib.h>

void firstnprimes(int *a, int n){

    if (n < 1){
        printf("INVALID");
        return;
    }

    int i = 0, j, k;                // i is the primes counter

    for (j = 2; i != n; j++){       // j is a candidate number

        for (k = 0; k < i; k++)
        {
            if (j % a[k] == 0)      // a[k] is k-th prime
                break;
        }

        if (k == i)                 // end-of-loop was reached
            a[i++] = j;             // record the i-th prime, j
    }
    return;
}

int main(){
    int n;
    scanf_s("%d",&n);
    int *a = (int *)malloc(n*sizeof(int));
    firstnprimes(a,n);
    for (int i = 0; i < n; i++)
        printf("%d\n",a[i]);
    system("pause");
    return 0;
}

我的函数的内部循环运行 i 次（最多），其中 i 是给定以下素数的个数候选数，外层循环运行 (nth prime number - 2) 次。

如何用大 O 表示法导出此算法的复杂性？

提前致谢。

Answer 1

素数定理渐进地指出，小于n的素数的个数等于n/log n。因此，您的内部循环将运行 Theta of i * max =n / log n * n 次（假设 max=n）。

此外，您的外循环运行大约 n log n 次，使得总复杂度 Theta 为 n / log n * n * n log n = n^3。也就是说，这不是最高效的算法。

请注意周围有更好的近似值（例如第 n 个素数更接近于：

n log n + n log log n - n + n log log n / log n + ...

但是，由于您只关心大 O，这个近似值就足够了。

此外，还有更好的算法来完成您想要做的事情。查找伪素数主题，了解更多信息。

Answer 2

在伪代码中你的代码是

firstnprimes(n) = a[:n]   # array a's first n entries
    where
       i = 0
       a = [j for j in [2..]  
                if is_empty( [j for p in a[:i] if (j%p == 0)] )
                   && (++i) ]

（假设一旦发现列表非空就短路is_empty which returns false）。

它所做的是测试从 2 开始的每个候选数字及其前面的所有素数。

Melissa O'Neill 分析了该算法 in her widely known JFP article 并得出其复杂度为 O( n^2 )。

基本上，产生的每个 n 个素数都与它前面的所有素数配对（由其测试）（即 k-1 个素数，对于第 k⟩ 个素数）和等差数列 0...(n-1) 的和是 (n-1)n/2 即 O( n^2 );她表明复合材料不会贡献任何比总和更重要的项，因为在通往第 n⟩ 个素数的路上有 O(n log n) composites 但 is_empty 计算 提前失败 他们。

事情是这样的：对于 m = n log n，将有 m/2 个偶数，对于每个其中 is_empty 计算仅需 1 步； m/3 3 的倍数，步长为 2； m/5 共 3 个步骤；等等

所以复合材料的总贡献，高估了，因为没有处理多重性（基本上，计算 15 两次，作为一个倍数3 和 5 等）的是：

SUM{i = 1, ..., n} (i m / p_i)          // p_i is the i-th prime
= m SUM{i = 1, ..., n} (i / p_i)
= n log(n) SUM{i = 1, ..., n} (i / p_i)
< n log(n) (n / log(n))                 // for n > 14,000 
= n^2

不等式可以在 Wolfram Alpha cloud sandbox 处测试为 Sum[ i/Prime[i], {i, 14000}] Log[14000.0] / 14000.0（即 0.99921，并且对于更大的 n，测试到 n = 2,000,000，其中 0.963554).

时间复杂度找到 n 个素数，尝试除以所有前面的素数

Time complexity finding n primes with trial division by all preceding primes

c

big-o

primes

time-complexity