Sieve Of Eratosthenes Algorithms
Implemented in any programming language
The sieve of Eratosthenes is a simple algorithm created by 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.
The algorithms below all compute prime numbers, but not all of them really implement excatly the Eratosthenes' algorithm.
Ada Awk Basic Bash C C++ C# D Caml Eiffel Euphoria F# Forth Fortran Go Haskell Java JavaScript Julia Lisp Lua Nim Oberon OCaml Oz Pascal Perl PHP Prolog Python Rebol Rexx Ruby Rust Scala Scheme Scriptol Smalltalk Swift 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]
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
Older Basic:
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
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 = (char *) 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;
}
C++
/* Sieve Of Erathosthenes by Denis Sureau */
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <vector>
void eratosthenes(int top) {
std::vector<int> all = { top };
int idx = 0;
std::cout
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 0)
{
count = 0;
for(i = 2; i
D
import std.stdio;
bool[8191] flags;
int main()
{
int i, count, prime, k, iter;
writeln("10 iterations");
for (iter = 1; iter
Source: Documentation du langage D.
Eiffel
class FIBONACCI
feature
fib (k: INTEGER): INTEGER is
require
pre_fib: k >= 0 do
if k = 0 then
Result := 0
else
if k = 1 then
Result := 1
else
Result := fib (k-2) + fib (k-1) end
end;
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 = 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
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
Go
(Selon la documentation du language)
func Generate(ch chan
Haskell
primes = sieve [ 2.. ]
where
sieve (p:x) = p : sieve [ n | n 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
JavaScript
<script language="JavaScript">
/* Sieve Of Erathosthenes by Denis Sureau */
function Eratosthenes(element, top)
{
var all = new Uint8Array(new ArrayBuffer(top));
var idx = 0;
var prime = 3;
var x, j;
element.innerHTML = "1 ";
while(prime
Julia
# Sieve of Erasthotenes in Julia
# By Denis Sureau 14/2/2014
function eratosthenes(size)
all=ones(Int32, size)
println(1)
println(2)
idx = 1
prime = 3
while prime
Source
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]
Nim
import math
proc eratosthenes(n): auto =
prime = newSeq[int8](n+1)
prime[0] = 1;
prime[1] = 1
for i in 0 .. int sqrt(float n):
if prime[i] == 0:
for j in countup(i*i, n, i):
prime[j] = 1
discard eratosthenes(1000)
Source: Hookrace/Converted from one of many Python solution.
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 []
| 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:=trunc(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
Source code
PHP
<?php
/* Sieve Of Erathosthenes by Denis Sureau */
function eratosthenes($n)
{
$all=array();
$prime=1;
echo 1," ",2;
$i=3;
while($i
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,")
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("\n")
eratosthenes(100)
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))
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 " "
Rust
fn sieve(bound: uint) -> ~[uint] {
let mut primes = std::vec::from_fn(bound+1, |num| num == 2 || num & 1 != 0);
for num in count(3u, 2).filter(|&num| primes[num]).take_while(|&num| num * num ()
}
fn main() {
assert_eq!(sieve(20), ~[2, 3, 5, 7, 11, 13, 17, 19]);
}
Source: jsanders on Github.
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
# Sieve of Eratosthènes by Denis Sureau
array sieve(int top)
array all = [ top ]
array somelist = [1]
int idx = 0
for int prime in 3 -- top step 2
if prime in all ? continue
somelist.push(prime)
int j = prime
while j
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)
Swift
func eratosthenes(n: Int) -> sieveResult {
var sieve = [Int] 0..< n
var i = 1
let top = Int(sqrt(Double(n)))
return sieveResult {
while ++i
Tcl
# By Sam Shen
set n 50
narray create sieve $n
sieve status
sieve map {
if ![]
{
inc = @0 + 2;
for (i = @0 + inc; i
See also:
Licence: © 2007-2015 Scriptol.com. Use
printed copies of this page freely on paper, do not duplicate it on the Web, add a link instead.
Programs on this page are public domain, or written by myself or contributed by users.