To find all prime numbers from 1 to N.

I know we usually approach this problem using Sieve of Eratosthenes, I had an alternate approach in mind using gcd that I wanted your views on.

My approach->

Keep a maintaining a variable if all prime numbers are processed till any iteration. If gcd of this var, number i ==1. That means the nos. are co-prime so i must be prime.

For ex: gcd(210,11) == 1, so 11 is prime. {210=2*3*5*7}

Pseudocode:

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)

Alternatively, we can also have a list and push the prime numbers into that list. SC = O(N) TC = O(N log(N)) [TC to calculate gcd using euclid's method => O(log(max(a,b)))]

Does this seem right or I am calculating the TC incorrectly here. Please post your views on this. TIA!

CodePudding user response：

Looks like the time complexity of my approach is closer to O(log^2(n)) as pointed out by many in the comments.

Also, the curr_gcd var would become quite large as N is increased and would definitely overflow int and long size limits.

Thanks to everyone who responded!

CodePudding user response：

Maybe your method is theoretically right,but evidently, it's not excellent.

It's efficiency is worse than SoE, the range of data that it needs is too large. So maybe it seems elegant to look but hard to use.

In my views, "To find all prime numbers from 1 to N" is already a well-known problem and that means it's solution is well considered.

At first, maybe we use brute-force to deal with it like this.

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;
        }
    }
}

it's a O(n^2) time algorithm.Too slow to endure.

Go ahead. We have SoE, which use O(nlognlogn) time.

But we have a better algorithm called "liner sieve", which only use O(n) time, just as it's name. I implement it with C language like this.

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;
        }
    }    
}

this O(n) algorithm is used by me to slove this kind of algorithm problems that appear in major IT companies and many kinds of OJ.