使用 GCD 查找从 1 到 N 的所有素数（埃拉托色尼筛的另一种方法）

Question

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

我知道我们通常使用埃拉托斯特尼筛法来解决这个问题，我想到了另一种使用 gcd 的方法，希望得到您的意见。

我的做法->

如果所有素数都被处理直到任何迭代，则保留一个维护变量。如果该变量的 gcd，则数字 i ==1。这意味着没有。是互质的，所以我一定是质数。

例如：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 => O(log(max(a,b)))]

这看起来正确还是我在这里错误地计算了 TC。请发表您对此的看法。 蒂亚！

Answer 1

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

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

感谢所有回复的人！

Answer 2

也许你的方法理论上是正确的，但显然，它并不出色。

它的效率比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中出现的这类算法问题的。