时间复杂度发现n个素数并尝试除以所有先前的素数 [英] Time complexity finding n primes with trial division by all preceding primes

问题描述

问题:查找 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 是给定候选数以下的质数的数量，外部循环运行第( n 个素数- 2 )次.

My function's inner loop runs for i times (at the most), where i is the number of prime numbers below a given candidate number, and the outer loop runs for (nth prime number - 2) times.

如何用Big O表示法推导该算法的复杂性?

How can I derive the complexity of this algorithm in Big O notation?

提前谢谢.

推荐答案

在伪代码中，您的代码是

In pseudocode your code is

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 会在发现列表为非空后立即返回 false ).

(assuming the short-circuiting is_empty which returns false as soon as the list is discovered to be non-empty).

它的工作是测试 2 中的每个候选编号，并按其所有前面的质数进行测试.

What it does is testing each candidate number from 2 and up by all its preceding primes.

Melissa O'Neill在她广为人知的中分析了该算法 JFP

Melissa O'Neill analyzes this algorithm in her widely known JFP article and derives its complexity as O( n^2 ).

基本上，每个产生的 n 素数都与它前面的所有素数(即 k-1 素数)配对(通过测试) k   th素数)和算术级数和 0 ...(n-1)的总和是(n-1)n/2 是 O(n ^ 2);并且她表明，组合不会贡献比总和重要的任何术语，因为存在

Basically, each of the n primes that are produced is paired up with (is tested by) all the primes preceding it (i.e. k-1 primes, for the k th prime) and the sum of the arithmetic progression 0...(n-1) is (n-1)n/2 which is O( n^2 ); and she shows that composites do not contribute any term which is more significant than that to the overall sum, as there are O(n log n) composites on the way to n th prime but the is_empty calculation fails early for them.

方法是这样的: m = n log n ，将有 m/2 个偶数，每个 is_empty 计算仅需 1 步骤； 3 的 m/3 倍数，包含 2 个步骤； m/5 和 3 个步骤；等等

Here's how it goes: with m = n log n, there will be m/2 evens, for each of which the is_empty calculation takes just 1 step; m/3 multiples of 3 with 2 steps; m/5 with 3 steps; etc.

因此，复合材料的总贡献被高估了，因为它们没有处理多重性(基本上，将 15 计数两次，是 3的倍数和 5 等)，是:

So the total contribution of the composites, overestimated by not dealing with the multiplicities (basically, counting 15 twice, as a multiple of both 3 and 5, etc.), is:

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云沙箱作为 Sum [i/Prime [i]，{i，14000}] Log [14000.0]/14000.0 (即 0.99921 ，而对于较大的 n 则减小，直到 n = 2,000,000 在 0.963554 处进行测试).

The inequality can be tested at Wolfram Alpha cloud sandbox as Sum[ i/Prime[i], {i, 14000}] Log[14000.0] / 14000.0 (which is 0.99921, and diminishing for bigger n, tested up to n = 2,000,000 where it's 0.963554).

这篇关于时间复杂度发现n个素数并尝试除以所有先前的素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！