Sieve of Eratosthenes – finding out all prime numbers up to N (Pascal)

This Pascal program finds out all the prime numbers up to a number N, by using a very efficient algorithm called The Sieve of Eratosthenes. How it works in short is that it goes through each number up to N, and if that number is prime, it marks all of its multiples as not prime. Thus, only the prime numbers are left unmarked and easy to recognize.
const max_number = 2000000;

var n,i,j:longint;
    is_prime:array[2..max_number] of boolean;

writeln('This program finds out all prime numbers up to a number n, by using the Sieve of Eratosthenes');
write('n='); readln(n);

{we first initialize the boolean array, marking all number as potential primes}
for i := 2 to n do is_prime[i] := true;

{after initializing, we apply the sieve}
for i := 2 to n do
  if (is_prime[i]) then
    write(i,' ');
    for j := 2 to trunc(n div i) do is_prime[i*j] := false; {this for loop marks all multiples up to n as being not prime}


Leave a Reply

Your email address will not be published. Required fields are marked *

16 − 7 =

This site uses Akismet to reduce spam. Learn how your comment data is processed.