CODEWITHSUNDEEP
algorithmloopssieve-of-eratosthenessieve-algorithm
tourist
tourist

Reputation: 544

Why is my Seive of Eratosthenes Algorithm implementation running into infinite loop?

I was implementing Sieve's Algorithm for finding Prime Numbers up to n. I am unable to find out why is it running into infinite loop.

Here I'm giving the code snippet. Please help.

for(int j=2;j<=Math.sqrt(n);j++){
  if(a[j]==true){
     int x=0;
     for(int p=(j*j+x*j); p<=n;x++){
        a[p]=true;
     }
  }
}

Upvotes: 1

Views: 70

Answers (2)

Adrian Colomitchi
Adrian Colomitchi

Reputation: 3992

Some optimisations suggestions:

// When j is 2, the bitwise (2 & 1) will be 0, so the cycle increments by 1
// When j is odd (from 3 and above), the cycle goes in steps of 2 
// (thus exploring only odd numbers)
// As a result, this cycle is twice as faster than the one progressing
// in increments of 1 
// See here --------------------V
for(int j=2;j<=Math.sqrt(n);j+=(j & 1 ? 2 : 1)) {
  if(a[j]==true){
     // int x=0; // what for?
     // a sum is cheaper than a multiplication
     // Here --V and here --V
     for(int p=j*j; p<=n;p+=j){
        a[p]=true;
     }
  }
}

Upvotes: 1

Caleth
Caleth

Reputation: 63019

Your inner loop is checking p but never changing it

Upvotes: 5

Related Questions