Algorithme du Crible d'Eratosthènes
Implémenté dans tous les langages de programmation.
Le crible d'Eratosthenes est un algorithme simple créé par Eratosthènes, un mathématicien de l'antiquité grecque, pour trouver les nombres premiers jusqu'à un entier donné. L'algorithme est souvent utilisé pour comparer la syntaxe des langages de programmation et la vitesse des compilateurs, ou interpréteurs.
L'algorithme:
Construire une liste de tous les entiers supérieurs à 1 et inférieurs ou égal à n. Supprimer les multiples de tous les premiers inférieurs ou égal à la racine carrée de n, ensuite, les nombres qui restent sont premiers.
En pseudo code (en fait en code Scriptol):
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
Afficher les premiers:
for int x in 0 .. n if a[x] echo " ", x /for print
Voir le code source
Si vous voulez utiliser l'algorithme pour évaluer et comparer des langages de programmation, implémentez le code ci-dessus. Les algorithmes ci-dessous calculent tous les nombres premiers, mais ils n'implémentent pas tous exactement l'algorithme d'Eratosthènes.
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, manuel de référence pour 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
Une autre 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);
}
}
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() )
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
Contribution à Scriptol.org
#!/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";
Code source
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)
Code sourceRebol
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)
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"); }
}
Voir aussi
- Le programme "Hello world!" (Salut le monde!) dans tous les langages de programmation.
- Histoire et évolution des langages pour ordinateur.
(c) 2001-2007 Denis G.Sureau
- Version originale Avril 2001.
Accueil
Accueil