Sieve Of Eratosthenes Algorithm

November 11, 2021 by No Comments

The sieve of Eratosthenes is a simple algorithm created by Eratosthenes, an ancient Greek mathematician, for finding all prime numbers up to a specified integer. The algorithm is often used to compare the syntax of programming languages and the speed of compilers, or interpreters.

The algorithm:

Build a list of all the integers greater than one and less than or equal to n. 
Strike out the multiples of all primes less than or equal to the square root of n, 
then the numbers that are left are the primes.

In pseudo code (really Scriptol code):

int n = 50
array a
int i, j
a[1] = 0
for i in 2 .. n let a[i] = 1
int p = 2
while (p * p) <= n
    j = p * p
    while j <= n 
       a[j] = 0
    let j + p
    do 
       p + 1
    until a[p] = 1
/while

Displaying the primes:

for int x in 0 .. n
   if a[x] echo " ", x
/for 
print

Get the source code

If you want to use the algorithm for benchmarking and comparing some programming languages, implement the code above. The algorithms below all compute prime numbers, but not all of them really implement exaltly the Eratosthenes’ algorithm.

 


Ada    Awk   Basic   Bash  C  C++  C#  Caml Eiffel  F#  Forth  Fortran  Haskell  Java  JavaScript   Lisp   Lua  Oberon  OCaml  Oz  Pascal  Perl  PHP  Prolog  Python  Rebol  Rexx  Ruby  Scala  Scheme  Scriptol  Smalltalk  Tcl


 

Ada

procedure Eratosthenes(Result : out Integer) is
   size : constant := 8190;
   k, prime : Natural;
   count : Integer;

   type Ftype is array (0 .. Size) of Boolean;
   Flags : Ftype;

begin
   for Iter in 1 .. 10 loop
      count := 0;

      for i in 0 .. size loop
         Flags (i) := True;
      end loop;

      for i in 0 .. size loop
         if Flags (i) then
            prime := i + i + 3;
            k := i + prime;
            while k <= size loop
               Flags (k) := False;
               k := k + prime;
            end loop;
            count := count + 1;
         end if;
      end loop;
   end loop;

   Result := count;
end Eratosthenes;

Awk

BEGIN {

    top = 50;
    n = (ARGV[1] < 1) ? 1 : ARGV[1];
    while (n--) 
    {
       for(i=2; i <= top; flags[i++]=1);
        for (i=2; i <= top; i++) 
        {
           if (flags[i]) 
           {
              for (k = i + i; k <= top; k += i) 
              {
                 flags[k] = 0;
              }
            }
        }
    }
    exit;
}

 

Basic

QuickBasic, reference manual for Apple Macintosh, by Microsoft.

defint a-z
size=50
dim flags(50)
for i=2 to size
  flags(i)=-1
next
for i=2 to sqr(size)
  if flags(i) then
    for k=i*i to size step i
      flags(k)=0
    next
  end if
next

for i=0 to size
  if flags(i) then print i;
next
print

Another version

1010 REM Quite BASIC Math Project
2000 CLS
2030 LET L = 50
2050 ARRAY N
2070 FOR I = 1 TO L 
2080 LET N[I] = I
2090 NEXT I
2110 LET P = 2
2120 PRINT P
2140 FOR I = P TO L STEP P
2150 LET N[I] = 0
2160 NEXT I
2180 LET P = P + 1
2190 IF P = L THEN END
2200 IF N[P] <> 0 THEN GOTO 2120 ELSE GOTO 2180

Bash

#!/bin/bash
# Sieve of Eratosthenes from the bash scripting guide 

UPPER_LIMIT=$1                  
let SPLIT=UPPER_LIMIT/2         

Primes=( '' $(seq $UPPER_LIMIT) )

i=1
until (( ( i += 1 ) > SPLIT ))  
do
  if [[ -n $Primes[i] ]]
  then
    t=$i
    until (( ( t += i ) > UPPER_LIMIT ))
    do
      Primes[t]=
    done
  fi  
done  
echo ${Primes[*]}

exit 0

C

/* Sieve Of Erathosthenes by Denis Sureau */
#include <stdlib.h> 
#include <stdio.h>

void eratosthenes(int top)
{
  int all[10000];
  int idx = 0;
  int prime = 3;
  int x, j;
		
  printf("1 ");
	
  while(prime <= top)
  {
    for(x = 0; x < top; x++)
    {
      if(all[x] == prime) goto skip; 
    }

    printf("%d ", prime);
    j = prime;
    while(j <= (top / prime))
    {
      all[idx++] = prime * j;
      j += 1;
    }

skip:	
    prime+=2;
  }
  puts("");
  return;
}

int main(int argc, char **argv)
{
  if(argc == 2) eratosthenes(atoi(argv[1]));
  else eratosthenes(50);
  return 0;
}

C++

/* Sieve Of Erathosthenes by Denis Sureau */
#include <stdlib.h> 
#include <stdio.h>
#include <iostream>
#include <vector>

void eratosthenes(int top)
{
  vector<int> all(top);
  int idx = 0;
	
  std::cout << "1 ";
	
  int prime = 3;
	
  while(prime <= top)
  {
    for(int x = 0; x < top; x++)
    {
      if(all[x] == prime) goto skip; 
    }

    std::cout << prime << " ";
    int j = prime;
    while(j <= (top / prime))
    {
      all[idx++] = prime * j;
      j += 1;
    }

skip:	
    prime+=2;
  }
  std::cout << std::endl;
  return;
}

int main(int argc, char **argv)
{
  if(argc == 2) eratosthenes(atoi(argv[1]));
  else eratosthenes(50);
  return 0;
}

C# (C Sharp)

using System;

class App 
{
    public static int Main(String[] args) 
    {        
        int num;
        bool[] flags = new bool[51];
        long i, k;
        int count = 0;
        
        num = System.Convert.ToInt32(args[0]);
        if(num < 1) num = 1;
        
        while(num-- > 0) 
        {
            count = 0;
            for(i = 2; i <= 50; i++) 
            {
                flags[i] = true;
            }
            for(i = 2; i <= 50; i++) 
            {
                if(flags[i]) 
                {
                    for(k = i + i; k <= 50; k += i) 
                    {
                        flags[k] = false;
                    }
                    count++;
                }
            }
        }
        
        Console.WriteLine("Count: " + count.ToString());
        return(0);
    }
}

F# (F Sharp)

let is_prime n =
  let max = int_of_float (Math.Sqrt( float_of_int n ))
  not ({ 2 .. max } |> Seq.filter ( fun d -> n%d = 0) |> Seq.nonempty)
let primes = [0 .. top] |> List.filter is_prime

Forth

7919 2/ constant maxp
: primes ( -- n )
  here maxp 1 FILL
  1 ( count, including 2 )
  maxp 0 DO
    I here + C@ IF
      I 2* 3 + ( dup .) DUP  I + ( prime current )
      begin  DUP maxp U<
      while  0 over here + C!
             over +
      repeat
      2drop 1+
    then
  loop ;

primes . \ 1000 

Fortran

*       Sieve of Eratosthenes by Chuck Bouldin
        top = 50

        logical*2 flags(top)
        integer*2 i,j,k,count,iter,prime
        n = long(362)                   
        do 92 iter = 1,10
           count=0
           i=0
           do 10 i = 1,top
10            flags(i) = .true.
           do 91 i = 1,top
              if (.not. flags(i)) go to 91
              prime = i + i + 3
              count = count + 1
              k = i + prime
              if (k .gt. top) go to 91
              do 60 j = k, top, prime
60               flags(j) = .false.
91          continue
92      continue
        write (9,*) count,” primes in”,(long(362)-n)/60.0,” seconds”
        pause
        end

Haskell

primes = sieve [ 2.. ]
  where
  sieve (p:x) = p : sieve [ n | n <- x, n `mod` p > 0 ]

Java

public class Eratosthenes 
{
    public static void main(String[] args) 
    { 
        int N = Integer.parseInt(args[0]);

        boolean[] isPrime = new boolean[N + 1];
        for (int i = 2; i <= N; i++)
            isPrime[i] = true;

        for (int i = 2; i*i <= N; i++) 
        {
            if (isPrime[i]) 
            {
                for (int j = i; i*j <= N; j++)
                    isPrime[i*j] = false;
            }
        }

        int primes = 0;
        for (int i = 2; i <= N; i++)
        {
           if (isPrime[i])
              System.out.println(" " + i);
        }
    }
}

JavaScript

<script language="JavaScript">

/* Sieve Of Erathosthenes by Denis Sureau */
 
function Eratosthenes(element, top)
{
  var all = new Array;
  var idx = 0;
  var prime = 3;
  var x, j;

  element.innerHTML = "1 ";
	
  while(prime <= top)
  {
	flag = true;
    	for(x = 0; x < top; x++)
    	{
      		if(all[x] == prime) 
		{
			flag = false;
			break;
		}	
    	}
	if(flag)
	{
		element.innerHTML += prime + " ";
		j = prime;
   		while(j <= (top / prime))
  		{
 			all[idx++] = prime * j;
			j += 1;
		}
	}
	prime += 2;
  }
  element.innerHTML += "
";
  return;
}
</script>


<div id="primediv" onclick="Eratosthenes(this, 50);">
Click to start...
</div>

 

Lisp

 (define divides (m n) (= (mod n m) 0))
 (define seq (m n) 
    (if (> m n) `() 
       (cons m (seq (+ 1 m) n))))
 (define remove-multiples (n L)
    (if (null? L) `()
        (if (divides (n (car l))
             (remove-multiples n (cdr L))
                 (cons (car L) 
                     (remove-multiples n (cdr L))))))

Lua

-- By Darren Kirby

x = arg[1]
y = math.floor(math.sqrt(x))
primes = {}
set = {}
for i=2,x do
    table.insert(set, i)
end

function isFactor(index, value)
    if math.mod(value, checkint) == 0 then 
        table.remove(set, index)
    end
end

while set[1] <= y do
    table.insert(primes, set[1])
    checkint = set[1]
    table.remove(set, 1)
    for i,v in ipairs(set) do isFactor(i,v) end
end 

for key, value in primes do
    io.write(value .. " ")
end

for key, value in set do
    io.write(value .. " ")
end
print()

 

Oberon

MODULE Eratosthenes; 
(*  Active Oberon Demo *)


IMPORT Streams;

CONST
	N = 50;
	Terminate = -1;
	
VAR log: Streams.Stream;

TYPE
	Sieve = POINTER TO SieveDesc;
	SieveDesc = RECORD (OBJECT)
	
		VAR prime, n: INTEGER; available: BOOLEAN; next: Sieve;
	
		PROCEDURE Set (i: INTEGER);
		BEGIN {EXCLUSIVE}
			PASSIVATE (~available); n := i; available := TRUE
		END Set;
		
		PROCEDURE Change;
		BEGIN {EXCLUSIVE} available := FALSE
		END Change;
	
		PROCEDURE & Init;
		BEGIN prime := 0; available := FALSE; next := NIL
		END Init;
		
	BEGIN {PARALLEL(2)}
		LOOP
			PASSIVATE (available);
			IF n = Terminate THEN
				IF next # NIL THEN next.Set (n) END;
				EXIT
			ELSE
				IF prime = 0 THEN 
					log.Int(n); log.Ln;
					prime := n; NEW (next)
				ELSIF (n MOD prime) # 0 THEN next.Set (n)
				END;
				Change
			END
		END
	END SieveDesc;
	
	Gen = POINTER TO GenDesc;
	GenDesc = RECORD
		VAR s: Sieve; i: INTEGER;
		
	BEGIN {PARALLEL(2)}
		NEW (s);
		FOR i := 2 TO N-1 DO s.Set (i) END;
		s.Set (Terminate)
	END GenDesc;
	
	PROCEDURE Start*;
	VAR g: Gen;
	BEGIN
		NEW(log, "Eratosthenes", 70);
		NEW (g)
	END Start;

END Eratosthenes.

Eratosthenes.Start			

Ocaml

(* (c) 2003 David Van Horn - Licensed under the Academic Free License version 2.0 *)

open List

type integer = Int of int
let number_two = Int(2)
let number_zero = Int(0)
let is_less_than_two (Int n) = n < 2
let incr (Int n) = Int(n + 1)
let decr (Int n) = Int(n - 1)
let is_number_zero (Int n) = n = 0

let iota n =
  let rec loop curr counter =
    if is_less_than_two counter then []
    else curr::(loop (incr curr) (decr counter))
  in
  loop number_two n

let sieve lst =
  let rec choose_pivot = function
  | [] -> []
  | car::cdr when is_number_zero car ->  
      car::(choose_pivot cdr)
  | car::cdr -> 
      car::(choose_pivot (do_sieve car (decr car) cdr))

  and do_sieve step current lst =
    match lst with 
    | [] -> []
    | car::cdr ->
	if is_number_zero current 
	then number_zero::(do_sieve step (decr step) cdr)
	else car::(do_sieve step (decr current) cdr)
  in
  choose_pivot lst

let is_prime n =
  match rev (sieve (iota n)) with
    x::_ -> not (is_number_zero x)

Oz

functor
import System Application

define Args N Flags Start Stop in

    [Args] = {Application.getArgs plain}
    N = {String.toInt Args}

    Start = 2
    Top = 50

    Flags = {BitArray.new Start Stop}
    for I in Start..Top do {BitArray.set Flags I} end

    for I in 1..N do
           for J in Start..Top do
            if {BitArray.test Flags J} then
                for K in J+J..Top;J do {BitArray.clear Flags K} end 
            end
        end
    end

   {System.showInfo "Count: "#{BitArray.card Flags}}

   {Application.exit 0}
end

Pascal

program Eratosthenes;

const N=1000;

var a:ARRAY[1..N] of boolean;
    i,j,m:word;

begin
 for i:=1 TO N do A[i]:=TRUE;
 m:=truncC(sqrt(N));
 for i:=2 to m do
   if a[i] then for j:=2 to N DIV i do a[i*j]:=FALSE;
 for i:=1 to N do if a[i] then write(i:4);
end.

Perl

use strict;
use integer;

my $num = $ARGV[0];
$num = 1 if ($num < 1);
my $count;
my top = 50
my @flags = ();

while($num--) 
{
    $count = 0; 
    my @flags = (0 .. top);
    for my $i (2 .. top ) 
    {
        next unless defined $flags[$i];
        for (my $k=$i+$i; $k <= top; $k+=$i) 
        {
            undef $flags[$k];
        }
        $count++;
    }
}
print "Count: $count\n";

PHP

<?php

/* Sieve Of Erathosthenes by Denis Sureau */

function eratosthenes($n)
{
   $all=array();
   $prime=1;
   echo 1," ",2;
   $i=3;
   while($i<=$n)
   {
        if(!in_array($i,$all))
         {
            echo " ",$i;
            $prime+=1;
            $j=$i;
            while($j<=($n/$i))
            {
               array_push($all,$i*$j);
               $j+=1;
            }
         }
        $i+=2;
   }
   echo "\n";
   return;
}

eratosthenes(50);
?>

 

Prolog

% Sieve of Eratosthene 
% Le Huitouze and Ridoux translated by DGS

$ erathostenes :- freeze(L,prime(L)),		
	list_of_ints(2,L).		

$ prime([X|L]) :-
	write(X), nl, 
	freeze(L,sieve(X,L,Canal)),	
  	freeze(Canal,prime(Canal)).	

$ sieve(X,[Nb|L],Canal) :-
	mod(Nb,X,0), !,			
	freeze(L,sieve(X,L,Canal)).	
					
$ sieve(X,[Nb|L],[Nb|Canal2]) :-	
	freeze(L,sieve(X,L,Canal2)).	

$ list_of_ints(X,[X|L]) :- 
	plus(X,1,X1),
	list_of_ints(X1,L)..

Python

def eratosthenes(n):

    all = []         
    prime = 1  

    print 1, 2,

    i = 3 
    while (i <= n):
        if  i not in all:
            print i,
            prime += 1
            j = i
            while (j <= (n / i)): 
                all.append(i * j)
                j += 1
        i += 2                        
    print

eratosthenes(50)

Rebol

ctr: to-integer to-string system/script/args
ctr: either ctr < 1 [ 1 ] [ ctr ]
top: 50

while [ ctr > 0 ] 
[
    flags: copy []
    for i 0 top 1 
    [
        insert tail flags 1
    ]
    flags: head flags

    for i 2 top 1 
    [
        p: pick flags i
        if p = 1 
        [
            k: i + i            
            while [ k <= top ] 
            [
                change at flags k 0
                k: k + i
            ]
        ]
    ]
    ctr: ctr - 1
]

Rexx

limit = 50
isPrime. = 1
do n=2 to limit
   if isPrime.n then
   call anotherPrime n
end
exit 0

anotherPrime 
  arg prime    
  say right( prime, length( limit ) )
  do multiple=prime by prime to limit
     isPrime.multiple = 0            
  end
return

Ruby

# sieve of Eratosthenes from the ruby distro
top = Integer(ARGV.shift || 100)
sieve = []
for i in 2 .. top
  sieve[i] = i
end

for i in 2 .. Math.sqrt(top)
  next unless sieve[i]
  (i*i).step(top, i) do |j|
    sieve[j] = nil
  end
end
puts sieve.compact.join " "

Scala

object Sieve 
 {
  def ints(n: Int): Stream[Int] =
    Stream.cons(n, ints(n+1))

  def primes(nums: Stream[Int]): Stream[Int] =
    Stream.cons(nums.head, primes ((nums tail) filter (x => x % nums.head != 0)) )

  def main(args: Array[String]): Unit = 
  {
    val n = Integer.parseInt(args(0))
    System.out.println(primes(ints(2)) take n toList)
  }
 }

Scheme

(define (sieve-of-eratosthenes n)
  (let ((table (make-bit-string (- n 2) #t)))
    (define (prime? k) (bit-string-ref table (- k 2)))
    (define (not-prime! k) (bit-string-clear! table (- k 2)))
    (loop ((for k (in-range (from 2) (up-to n))))
      (if (prime? k)
          (loop ((for i (in-range (from (* 2 k)) (up-to n) (by k))))
            (not-prime! i))))
    (collect-list (for k (in-range (from 2) (up-to n)))
        (if (prime? k))
      k))) 

Scriptol

void eratosthenes(int n)
    int [] all = {}         
    int prime = 1  

    echo 1, " ", 2

    int i = 3 
    while i <= n
        if  i not in all:
            echo " ", i
            prime + 1
            int j = i
            while j <= (n / i)
                all.push(i * j)
            let j + 1
	/if	
    let  i + 2                        
    print
return	

eratosthenes(50)

Source code

Smalltalk

" Sieve of Erastosthenes in Smalltalk by Rob Hoelz

Object subclass: #Sieve
    instanceVariableNames: 'primes'
    classVariableNames: ''
    poolDictionaries: ''
    category: nil.

!Sieve class methodsFor: 'instance creation'!

new: limit
    |r|

    r := super new.
    r init: limit.
    ^r
! !

!Sieve methodsFor: 'instance initialization'!
init: limit
    primes := Array new: limit.
    primes at: 1 put: 0.
    2 to: limit do: [:x| primes at: x put: 1]
! !

!Sieve methodsFor: 'prime generation'!
generate
    |currPrime|

    currPrime := 2.
    [((currPrime * currPrime) <= (primes size))] whileTrue: [self removeMultiples: currPrime. currPrime := self nextPrime: currPrime]
! !

!Sieve methodsFor: 'printing'!
printPrimes
    |index|

    index := 1.
    primes do: [:x| (x = 1) ifTrue: [Transcript show: (index displayString). Transcript show: ' ']. index := index + 1].
    Transcript cr
! !

!Sieve methodsFor: 'private'!
removeMultiples: currPrime
    |index|

    index := currPrime * 2.
    [(index <= (primes size))] whileTrue: [primes at: index put: 0. index := index + currPrime]
!
nextPrime: currPrime
    |index|

    index := currPrime + 1.
    [(index <= (primes size))] whileTrue: [(1 = (primes at: index)) ifTrue: [^index]. index := index + 1].
    ^(primes size)
! !

|argv limit s|
argv := Smalltalk arguments.
limit := (argv at: 1) asInteger.
s := Sieve new: limit.
s generate.
s printPrimes.

 

Tcl

# By Sam Shen
set n 50
narray create sieve $n
sieve status
sieve map {
    if ![] 
    {
        inc = @0 + 2;
        for (i = @0 + inc; i < @#0; i += inc) 
        {
            [i] = 1;
        }
    }
}
sieve map 
{
    if ![] 
    {
        printf("%4d ", @0 + 2);
    }
    post { printf("\n"); }
}

See also

  • Hello world programs in any programming languages
  • History and evolution or computer languages

External links

  • Literate programs. Some implementations come from this website.