使用GCD查找从1到N的所有素数（筛选eratothenes的另一种方法）

Question

查找从1到N的所有素数。

我知道我们通常使用厄拉多塞的筛子来处理这个问题，我有一个使用gcd的替代方法，我想听听你的意见。

我的方法-

如果所有质数都被处理到任何迭代，则保留一个保持变量。如果这个var的gcd，那么数字i==1。这意味着数字是co-prime，所以i必须是prime。

For ex: gcd(210，11) == 1，所以11是素数。{210=2*3*5*7}

伪代码：

Init num_list={contains numbers 2 to N} [since 0 and 1 arent prime nos.]
curr_gcd = 2, gcd_val=1
For i=3;i<=N;i++
    gcd_val=__gcd(curr_gcd,i)
    if gcd_val == 1 //(prime)
          curr_gcd = curr_gcd * i
    else //(composite so remove from list)
         numList.remove(i)

或者，我们也可以有一个列表，并将质数推送到该列表中。SC=O（N）TC=O（N-log（N））[TC使用欧氏方法计算gcd=

这看起来对吗，或者我在这里计算TC不正确。请就此发表你的看法。蒂亚！

Answer 1

也许你的方法理论上是正确的，但很明显，它并不优秀。

它的效率比SoE差，它需要的数据范围太大。所以也许它看起来很优雅，但很难使用。

在我看来，“找出从1到N的所有素数”已经是一个众所周知的问题，这意味着它的解决方案是经过深思熟虑的。

起初，也许我们用蛮力来处理它。

int primes[N],cnt;//store all prime numbers
bool st[N];//st[i]:whether i is rejected
void get_primes(int n){
    for(int i=2;i<=n;i++){
        if(st[i]) continue;
        primes[cnt++]=i;
        for(int j=i+i;j<=n;j+=i){
            st[j]=true;
        }
    }
}

这是一个O（n^2）时间算法。太慢了，无法忍受。

请便。我们有SOE，它使用O（nlognlogn）时间。

但是我们有一个更好的算法叫做“线性筛”，它只用O(n)时间，正如它的名字一样。我是这样用C语言实现的。

int primes[N],cnt;
bool st[N];
void get_primes(int n){
    for(int i=2;i<=n;i++){
        if(!st[i]) primes[cnt++]=i;
        for(int j=0;primes[j]*i<=n;j++){
            st[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }    
}

这个O（n）算法被我用来爱上这种出现在主要IT公司和许多OJ中的算法问题。

Answer 2

看起来我的方法的时间复杂度更接近O（log^2（n）），正如许多人在评论中指出的那样。

此外，随着N的增加，curr_gcd变量会变得非常大，并且肯定会溢出int和long大小限制。

感谢所有回复的人！