CODEWITHSUNDEEP
primesalgol
user29568
user29568

Reputation: 167

Is this program to find prime numbers wrong?

While reading “Code: The Hidden Language of Computer,” I came across the ALGOL program that the author included to find the prime numbers through 10,000 using the Sieve algorithm. Below is the code. 

begin
   Boolean array a[2:10000];
   integer i, j;

   for i :=2 step 1 until 10000 do
       a[i] :=true;

   for i :=2 step 1 until 100 do
       if a[i] then 
            for j := 2 step 1 until 10000 / i do
                a[i*j] :=false;
   for i :=2 step 1 until 10000 do
       if a[i] then
           print(i);
end

When I usually see a program I test it by using real values to see its validity. In this case, the concern I have is with the line For j:=..... If we take i as 3 and 3 as the specific point in the steps of j. Then j would be 1. So, a[i*j], i.e., a[3], would be false when it should be true since its a prime. Can j or i be equal to 1?

Am I missing something over here? I would appreciate any help.

Upvotes: 0

Views: 244

Answers (2)

Mohak Gupta
Mohak Gupta

Reputation: 193

If anyone is interested here is a slightly faster implementation of this algorithm

#include <iostream>
#include <vector>
using namespace std;
long long sumPrime(long long n){
   
    vector<long long> isPrime(n+1,true);
    for (long long i = 2; i <= n; i++) {
        if(isPrime[i]){
            cout<<i<<" ";
        }
        for (long long j = i*i; j <= n; j=j+i) {
            isPrime[j]=false;
        }
    }
    
}



int main() {
    cout<<sumPrime(2000000);
    return 0;
}

Upvotes: 0

nullptr
nullptr

Reputation: 11058

for j := 2
         ^

j starts at 2, so only non-prime numbers' indexes (i*2, i*3, ...) would be set to false in the array.

Upvotes: 1

Related Questions