CODEWITHSUNDEEP
c++algorithmmathprimes
Soda Fries
Soda Fries

Reputation: 11

Should I keep this function for finding nth prime or can this be optimized?

We have a coding homework related to prime and my friend wrote this code. Its long and I dont understand it that much and has goto which is I think frowned upon so I don't know. Can help decide if we should we keep it?

int getNth (int nth){
    vector<int> prime;
    int sievelmt = nth*10;
    int i,j;
    func:
    vector<int> sieve(sievelmt, -1);
    prime.push_back(2); if (nth == 1) return 2;
    prime.push_back(3); if (nth == 2) return 3;
    prime.push_back(5); if (nth == 3) return 5;
    for (i = 2; i <= sievelmt; i++)
    {
        if (i%2==0||i%3==0||i%5==0) continue;
        if (sieve[i] == -1)
        {
            prime.push_back(i); if (prime.size()==nth) return prime[prime.size()-1];
            for ( j = 1; i*j <= sievelmt; j++) sieve[i*j]=j;
        }
        else continue;
    }    
    sievelmt *= 10;
    sieve.clear(); prime.clear();
    goto func;
    return -1;
}

Upvotes: 1

Views: 85

Answers (1)

Jean-Baptiste Yun&#232;s
Jean-Baptiste Yun&#232;s

Reputation: 36441

The heart of the algorithm is this line:

for ( j = 1; i*j <= sievelmt; j++) sieve[i*j]=j;

For a given i that fills locations of array sieve that are multiples of i, with the rank of the multiple. Imagine i=7, then sieve[7]=1, sieve[14]=2, sieve[21]=3, etc.

This is the base of Eratosthène's sieve, a very very old algorithm (Eratosthène was an ancient Greek scientist) to find primes. If you make i vary from 2 to some value, then this will mark every location whose index is not prime. At the end, every location not marked is then a prime. Let see:

  • i=2 .1.2.3.4.5.6.7.
  • i=3 .112.2.435.4.75, 3 is prime (first time location 3 has been visited)
  • i=4 .111.2.235.3.75
  • i=5 .11112.232.3.73, 5 is prime (first time location 5 has been visited)
  • i=6 .11111.232.3.73
  • i=7 .111111232.3.23, 7 is prime
  • i=8 .111111132.3.23
  • i=9 .111111112.3.23
  • i=10 .111111111.3.23
  • i=11 .11111111113.23, 11 is prime
  • etc.

Why is there a goto here? Don't worry, there exists numerous dangerous usage of goto, but that one is not. If you don't feel ok with that one replace:

func:
...
goto func;

with:

while(1) {
...
}

So the real question is why there is some "infinite" loop other there?

This is because you are looking for the n-th prime, but you can't easily determine how long the array must be to be able to capture the n-th prime... So that implementation just tries with increasing sizes. The first time, algorithm hopes that the n-th prime will be in an array of size 10*n, if it is not sufficient, then the size is mutiplied by 10, again, and again, until the n-th prime will be in.

Could I optimize this?

Sure, there is some little tricks. First you can see that if a given i it is divisible by 2, 3 or 5, then it can't be prime. That has already been implemented:

if (i%2==0||i%3==0||i%5==0) continue;

Then you may say, ok if divisible by 7 or 11 or 13, etc (means by any other prime), it's the same! I will not tell you more, but of course you can transform that algorithm to determine if a given i is or not divisible by any prime less then i (maybe by storing slightly different values in the array).

Upvotes: 1

Related Questions