Алгоритм критерия Эратосфена
Реализован во всех языках программирования
Сорт Эратостена - простой алгоритм, созданный математиком древнегреческой древности, для поиска простых чисел вплоть до данного целого числа. Алгоритм часто используется для сравнения синтаксиса языков программирования и скорости компиляторов, или интерпретаторов.
Алгоритм:
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.
Алгоритмы ниже вычисляют все простые числа, но все они не реализуют точно алгоритм Эратосхена.
Ada Awk Basic Bash C C P Prolog Python Rebol Rexx Ruby Rust Scala Scribtol Scalltalk Swift Tcl WLangage
Ада
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
En Basic plus ancien:
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; }
Une autre version sans goto proposée par un utilisateur:
#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 << "1 "; for(int prime = 3; prime <= top; prime += 2) { bool flag = false; for(int x = 0; x < top; x++) { if(all[x] == prime) { flag = true; break; } } if(flag == false) { std::cout << prime << " "; int j = prime; while(j <= (top / prime)) { all[idx++] = prime * j; j += 1; } } } 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);
}
}
D
import std.stdio;
bool[8191] flags;
int main()
{
int i, count, prime, k, iter;
writeln("10 iterations");
for (iter = 1; iter <= 10; iter++)
{
count = 0;
flags[] = 1;
for (i = 0; i < flags.length; i++)
{
if (flags[i])
{
prime = i + i + 3;
k = i + prime;
while (k < flags.length)
{
flags[k] = 0;
k += prime;
}
count += 1;
}
}
}
writefln("%d primes", count);
return 0;
}
Source: D language Documentation.
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 <= 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
Go
(Selon la documentation du language)
func Generate(ch chan<- int) {
for i := 2; ; i++ {
ch <- i
}
}
func Filter(in <-chan int, out chan<- int, prime int) {
for {
i := <-in // Receive value from 'in'.
if i%prime != 0 {
out <- i
}
}
}
func main() {
ch := make(chan in
go Generate(ch)
for i := 0; i < 10; i++ {
prime := <-ch
fmt.Println(prime)
ch1 := make(chan int)
go Filter(ch, ch1, prime)
ch = ch1
}
}
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 Uint8Array(new ArrayBuffer(top));
var idx = 0;
var prime = 3;
var x, j;
element.innerHTML = "1 ";
while(prime <= top var 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 ="<br>" return lt script gt lt div id="primediv" onclick="Eratosthenes(this, 50);" gt Click to start... lt div gt pre>
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 <= size
if !in(prime, all)
println(prime)
idx += 1
j = prime
while (j <= (size / prime))
all = [all, prime * j]
j += 1
end
end
prime += 2
end
println
end
eratosthenes(50)
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()
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/Conversion d'une des nombreuses solutions en Python.
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:=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
Contribution des utilisateurs.
#!/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 3
def eratosthenes(n):
all = []
prime = 1
print(1)
print(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(1000)
Contribution d'un utilisateur plus conforme à l'algorithme du crible d'Eratosthène:
# 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 <= bound) {
for j in range_step_inclusive(num*num, bound, num) {
primes[j] = false;
}
}
primes.move_iter().enumerate().skip(2).filter_map(|(i, p)| if p {Some(i)} else {None}).collect::<~[uint]>()
}
fn main() {
assert_eq!(sieve(20), ~[2, 3, 5, 7, 11, 13, 17, 19]);
}
Source: jsanders sur 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)))
# Sieve of Eratosthenes par 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 <= (top / prime)
all[idx] = prime * j
idx + 1
j + 1
/while
/for
return somelist
array a = sieve(1000)
print a
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.
Swift
func eratosthenes(n: Int)-> sieveResult {
var sieve = [Int] 0 ..< n
var i = 1
let top = Int(sqrt(Double(n)))
return sieveResult {
while ++i < n {
if sieve[i] != 0 {
if i <= top {
for notPrime in stride(from: i*i, to: n, by: i) {
sieve[notPrime] = 0
}
}
return i
}
}
return nil
}
}
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"); }
}
WLangage
Proposé par l'auteur:
(c) 2010 Jacques De Schryver
Licensed under the Academic Free License.
i, j, k sont entiers = 1
tantque i <= 1000
i += (1 + (i>2))
k = 1
POUR j = 2 A Racine(i)
SI i modulo j = 0 ALORS k = 0
FIN
SI k = 1 ALORS Description_de_l_erreur += i + " ; "
FIN
Voir aussi
- Le programme "Hello world!" (Salut le monde!) dans tous les langages de programmation.
- Histoire et évolution des langages pour ordinateur.
Licence: (c) 2007-2015 .fr. Utilisez librement des copies de cette page sur papier, ne la dupliquez pas sur le Web, placez plutôt un lien.
Les programmes sont du domaine public ou écrit par moi-même ou contribués par les utilisateurs.
Les programmes sont du domaine public ou écrit par moi-même ou contribués par les utilisateurs.