查找从1到N的所有素数
我知道我们通常使用埃拉托斯特尼筛来解决这个问题，我想用gcd来解决另一种方法，我想听听你的意见。
我的方法->
如果所有素数都被处理到任何迭代，则保持一个保持变量。如果这个变量的gcd，则数字i==1。这意味着数是同素的，所以我一定是素的。
对于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＝>O(log(max(a，b((]
这看起来正确吗？或者我在这里计算TC不正确。请发表你对此的看法。TIA！
正如许多人在评论中指出的那样，我的方法的时间复杂性似乎更接近O(log^2(n((。
此外，随着N的增加，curr_gcd var将变得相当大，并且肯定会溢出int和long大小限制。
感谢所有回应的人！
也许你的方法理论上是正确的，但显然，它并不优秀。
它的效率比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中的算法问题。