Sieve Of Eratosthenes Algorithm

Implemented in any programming language

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 Euphoria 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;
}

Another version with no goto submitted by an user:

#include <stdio.h>
#include <stdlib.h>

/* Sieve by Baavgai */
void sieve(int size) {
       int i,j;
       char *sieve = calloc(size, 1);
       for (i=2; i*i <= size; i++) {
               if (!sieve[i]) {
                       for(j = i+i; j < size; j+=i) { sieve[j] = 1; }
               }
       }
       for (i=2; i<size; i++) {
               if (!sieve[i]) { printf("%d ", i); }
       }
       printf("\n");
       free(sieve);
}
int main() {
       sieve(100);
       return 0;
}

Source.

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);
    }
}

Euphoria

-- Sieve Of Erathosthenes by Derek Parnell
-- Language: Euphoria v3.1.1 (www.rapideuphoria.com)
include get.e
procedure eratosthenes(integer target)

 sequence sieve
 integer next_prime
 integer limit

 sieve = repeat(0, target)
 limit = floor(power(target, 0.5))
 sieve[1] = 1
 next_prime = 2
 while next_prime <= target and next_prime != 0 do
   if next_prime <= limit then
     for i = next_prime + next_prime to target by next_prime do
         sieve[i] = 1
       end for
   end if
   printf(1, "%d ", next_prime)
   next_prime = find_from(0, sieve, next_prime+1)
 end while

 return
end procedure

procedure main(sequence argv)
 integer n

 n = 50
 if length(argv) >= 3 then
   argv = value(argv[3])
   n = argv[2]
 end if

 eratosthenes(n)
end procedure

main( command_line() )

Source code

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>

Source code

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

Contributed by users:


#!/usr/bin/perl

use strict;
use integer;

my $count = 0;
my $top = 50;
my @flags = (0 .. $top);

for my $i (2 .. int(sqrt($top)) + 1)
{
       next unless defined $flags[$i];
       for (my $k=$i+$i; $k <= $top; $k+=$i)
       {
           undef $flags[$k];
       }
}

print "Here is the list of primes from 1 to $top:\n";
for my $j ( 1 .. $top)
{
       print ("$j ") && $count++ if defined
$flags[$j];
}
print "\n";
print "Number of primes found: $count\n";

Source code

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);
?>

Source code

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 3

def eratosthenes(n):
    all = []         
    prime = 1  
    print("1, 2,", sep='', end='')
    i = 3 
    while (i <= n):
        if  i not in all:
            print(i, ",", sep='',end='')
            prime += 1
            j = i
            while (j <= (n / i)): 
                all.append(i * j)
                j += 1
        i += 2                        
    print("\n")

eratosthenes(100)

Source code

Contribution by a user, more conformant to the Sieve of Erastosthenes algorithm:

# Sieve by Baavgai
  
def eratosthenes(n):
       sieve = [ True for i in range(n+1) ]
       def markOff(pv):
               for i in range(pv+pv, n+1, pv):
                       sieve[i] = False
       markOff(2)
       for i in range(3, n+1):
               if sieve[i]:
                       markOff(i)
       return [ i for i in range(1, n+1) if sieve[i] ]

print(eratosthenes(100))

Source code

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"); }
}