Sieve of Erathostenes Back to the Win32 Shootout Back to dada's perl lab

[The Original Shootout]   [NEWS]   [FAQ]   [Methodology]   [Platform Details]   [Acknowledgements]   [Scorecard]
All Source For Sieve of Erathostenes
sieve.awka
```# \$Id: sieve.gawk,v 1.10 2001/05/25 03:33:08 doug Exp \$
# http://www.bagley.org/~doug/shootout/

BEGIN {
n = (ARGV[1] < 1) ? 1 : ARGV[1];
while (n--) {
count=0;
for(i=2; i <= 8192; flags[i++]=1);
for (i=2; i <= 8192; i++) {
if (flags[i]) {
# remove all multiples of prime: i
for (k=i+i; k <= 8192; k+=i) {
flags[k] = 0;
}
count++;
}
}
}
printf("Count: %d\n", count);
exit;
}
```
sieve.bcc
```/* -*- mode: c -*-
* \$Id: sieve.gcc,v 1.7 2001/05/06 04:37:45 doug Exp \$
* http://www.bagley.org/~doug/shootout/
*/

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

int
main(int argc, char *argv[]) {
int NUM = ((argc == 2) ? atoi(argv[1]) : 1);
static char flags[8192 + 1];
long i, k;
int count = 0;

while (NUM--) {
count = 0;
for (i=2; i <= 8192; i++) {
flags[i] = 1;
}
for (i=2; i <= 8192; i++) {
if (flags[i]) {
// remove all multiples of prime: i
for (k=i+i; k <= 8192; k+=i) {
flags[k] = 0;
}
count++;
}
}
}
printf("Count: %d\n", count);
return(0);
}

```
sieve.bigforth
```\ \$Id: sieve.bigforth,v 1.1 2001/06/19 16:20:46 doug Exp \$
\ http://www.bagley.org/~doug/shootout/
\ adapted from a program in the gforth distribution
\ modified and annotated by doug bagley

\ find and count all primes from 2 to 8192

decimal

\ read NUM from last command line argument
0. argc @ 1- arg >number 2drop drop constant NUM

\ we search for primes up to this SIZE
8192 constant SIZE

\ Flags is an array of chars of length SIZE
\ we'll mark all non-prime indexes in this array as false
\ the remaining indexes will be prime numbers
create Flags SIZE allot

\ EndFlags points to end of array Flags
Flags SIZE + constant EndFlags

\ FLAGMULTS
\ flag all multiples of n in array as not prime
\ starting value for fromaddr should be
\   arraystart n n + +
: flagmults
do
0 i c! dup
+loop ;
\ END FLAGMULTS

\ PRIMES
\ find all primes from 2 to SIZE
: primes
\ fill array Flags with 1's
Flags SIZE 1 fill
0 2
\ index i ranges from Flags to EndFlags
EndFlags Flags
do
i c@
\ If the current Flags[i] is true (i.e. i is prime)
if
dup i + dup EndFlags <
\ If we aren't at end of flags array yet
if
EndFlags swap flagmults
else
drop
then
\ Increment our Count of Primes
swap 1+ swap
then
1+
loop
;
\ END PRIMES (Returns: Count)

\ BENCHMARK
\ run the test NUM times
: benchmark  0 NUM 0 do  primes nip loop ;

\ now print count of how many Flags are now "true"
." Count: " benchmark  1 u.r cr

\ PPRIMES
\ for testing, we can print out all the prime numbers
: pprimes
SIZE 0 do Flags i + c@ if i 2 + . then loop cr ;

\ uncomment the following to print the primes or debug
\ pprimes
\ flags 100 dump

bye \ th-th-that's all folks!
```
sieve.csharp
```// \$Id: sieve.csharp,v 1.0 2002/02/14 14:02:00 dada Exp \$

using System;

class App {
public static int Main(String[] args) {
int NUM;
bool[] flags = new bool[8193];
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 <= 8192; i++) {
flags[i] = true;
}
for(i=2; i <= 8192; i++) {
if(flags[i]) {
// remove all multiples of prime: i
for(k=i+i; k <= 8192; k+=i) {
flags[k] = false;
}
count++;
}
}
}

Console.WriteLine("Count: " + count.ToString());
return(0);
}
}
```
sieve.cygperl
```#!/usr/local/bin/perl
# \$Id: sieve.perl,v 1.10 2001/05/06 04:37:45 doug Exp \$
# http://www.bagley.org/~doug/shootout/

use strict;
use integer;

# Tony Bowden suggested using 0..8192 to create the array
# and to test for defined instead of the value.

my \$NUM = \$ARGV[0];
\$NUM = 1 if (\$NUM < 1);
my \$count;
my @flags = ();
while (\$NUM--) {
\$count = 0;
my @flags = (0 .. 8192);
for my \$i (2 .. 8192 ) {
next unless defined \$flags[\$i];
# remove all multiples of prime: i
for (my \$k=\$i+\$i; \$k <= 8192; \$k+=\$i) {
undef \$flags[\$k];
}
\$count++;
}
}
print "Count: \$count\n";
```
sieve.delphi
```program sieve;

const MAX = 8192;

var NUM, code, i, n, k, count: integer;
flags : array[0..MAX] of boolean;
begin
NUM :=1;
if ParamCount=1 then
Val(ParamStr(1),NUM,code);

for n:=1 to NUM do begin
count := 0;
fillChar(flags,sizeof(flags),True);
for i := 2 to MAX do
if flags[i] then begin
inc(Count);
k:=i+i;
while k<=MAX do begin
flags[k]:=false;
inc(k,i);
end;
end;
end;
WriteLn('Count: ',Count);
end.

```
sieve.elastic
```// \$Id: sieve.elastic,v 1.0 2002/05/17 10:07:00 dada Exp \$
package sieve;

import basic;
import sys;
import array;

private n = 1;
private i, k;
private result = 0;
private flags = #[];
private count;
if(array.length(sys.args) > 0) {
n = basic.int(sys.args[0]);
} else {
n = 1;
}
while(n--) {
count = 0;
for (i=2; i <= 8192; i++) {
flags[i] = 1;
}
for (i=2; i <= 8192; i++) {
if (flags[i]) {
// remove all multiples of prime: i
for (k=i+i; k <= 8192; k=k+i) {
flags[k] = 0;
}
count++;
}
}
}
basic.print("Count: ", count);
```
sieve.erlang
```%%% -*- mode: erlang -*-
%%% \$Id: sieve.erlang,v 1.12 2000/10/07 08:41:44 doug Exp \$
%%% http://www.bagley.org/~doug/shootout/

-module(sieve).
-export([main/0, main/1]).
-import(io, [fwrite/2]).
-import(lists, [seq/2]).
-import(math, [sqrt/1]).

%% get the program argument, which is how many test iterations
%% to run
main() -> main(['1']).
main(Arg) ->
[Tmp] = Arg,
Num = list_to_integer(atom_to_list(Tmp)),
test(Num),
halt(0).

test(N) ->
Primes = primes(8192),
Count = length(Primes),
case N > 1 of
true  -> test(N-1);
false -> fwrite("Count: ~w\n", [Count])
end.

primes(Size) ->
era(sqrt(Size), seq(2,Size)).

%% modified from Maurice Castro's original (below), sped it up
%% a fraction by reordering clauses and args, but if it's less
%% clear now, that's my fault.
%% -Doug

era(Max, [H|T]) when H =< Max ->
[H | era(Max, sieve([H|T], H))];
era(Max, L) ->
L.

sieve([H|T], N) when H rem N =/= 0 ->
[H | sieve(T, N)];
sieve([H|T], N) ->
sieve(T, N);
sieve([], N) ->
[].

%%% eratosthenes algorithm from Maurice Castro, with permission,
%%% from his book, _Erlang in Real Time_, ISBN: 0864447434
%%% http://www.serc.rmit.edu.au/~maurice/erlbk/eg/choice/erasto.erl
%
%era(Max, L) when hd(L) =< Max ->
%    Prime = hd(L),
%    [Prime | era(Max, sieve(Prime, L))];
%era(Max, L) ->
%    L.
%
%sieve(N, []) ->
%    [];
%sieve(N, [H|T]) when H rem N == 0 ->
%    sieve(N, T);
%sieve(N, [H|T]) ->
%    [H | sieve(N, T)].
```
sieve.fpascal
```program sieve;
uses SysUtils;

var
NUM, i, k, count : integer;
flags : array[0..8192] of integer;

begin
if ParamCount = 0 then
NUM := 1
else
NUM := StrToInt(ParamStr(1));

if NUM < 1 then NUM := 1;

while NUM > 0 do
begin
Dec(NUM);
count := 0;
for i := 0 to 8192 do
begin
flags[i] := i;
end;
for i := 2 to 8192 do
begin
if flags[i] <> -1 then
begin
k := i+i;
while k <= 8192 do
begin
flags[k] := -1;
Inc(k, i);
end;
Inc(count);
end;
end;
end;
WriteLn('Count: ' + IntToStr(Count));
end.
```
sieve.gawk
```# \$Id: sieve.gawk,v 1.10 2001/05/25 03:33:08 doug Exp \$
# http://www.bagley.org/~doug/shootout/

BEGIN {
n = (ARGV[1] < 1) ? 1 : ARGV[1];
while (n--) {
count=0;
for(i=2; i <= 8192; flags[i++]=1);
for (i=2; i <= 8192; i++) {
if (flags[i]) {
# remove all multiples of prime: i
for (k=i+i; k <= 8192; k+=i) {
flags[k] = 0;
}
count++;
}
}
}
printf("Count: %d\n", count);
exit;
}
```
sieve.gcc
```/* -*- mode: c -*-
* \$Id: sieve.gcc,v 1.7 2001/05/06 04:37:45 doug Exp \$
* http://www.bagley.org/~doug/shootout/
*/

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

int
main(int argc, char *argv[]) {
int NUM = ((argc == 2) ? atoi(argv[1]) : 1);
static char flags[8192 + 1];
long i, k;
int count = 0;

while (NUM--) {
count = 0;
for (i=2; i <= 8192; i++) {
flags[i] = 1;
}
for (i=2; i <= 8192; i++) {
if (flags[i]) {
// remove all multiples of prime: i
for (k=i+i; k <= 8192; k+=i) {
flags[k] = 0;
}
count++;
}
}
}
printf("Count: %d\n", count);
return(0);
}

```
sieve.gforth
```\ \$Id: sieve.gforth,v 1.2 2001/05/25 16:49:59 doug Exp \$
\ http://www.bagley.org/~doug/shootout/
\ adapted from a program in the gforth distribution
\ modified and annotated by doug bagley

\ find and count all primes from 2 to 8192

decimal

\ read NUM from last command line argument
0. argc @ 1- arg >number 2drop drop constant NUM

\ we search for primes up to this SIZE
8192 constant SIZE

\ Flags is an array of chars of length SIZE
\ we'll mark all non-prime indexes in this array as false
\ the remaining indexes will be prime numbers
create Flags SIZE allot

\ EndFlags points to end of array Flags
Flags SIZE + constant EndFlags

\ FLAGMULTS
\ flag all multiples of n in array as not prime
\ starting value for fromaddr should be
\   arraystart n n + +
: flagmults
do
0 i c! dup
+loop ;
\ END FLAGMULTS

\ PRIMES
\ find all primes from 2 to SIZE
: primes
\ fill array Flags with 1's
Flags SIZE 1 fill
0 2
\ index i ranges from Flags to EndFlags
EndFlags Flags
do
i c@
\ If the current Flags[i] is true (i.e. i is prime)
if
dup i + dup EndFlags <
\ If we aren't at end of flags array yet
if
EndFlags swap flagmults
else
drop
then
\ Increment our Count of Primes
swap 1+ swap
then
1+
loop
;
\ END PRIMES (Returns: Count)

\ BENCHMARK
\ run the test NUM times
: benchmark  0 NUM 0 do  primes nip loop ;

\ now print count of how many Flags are now "true"
." Count: " benchmark  1 u.r cr

\ PPRIMES
\ for testing, we can print out all the prime numbers
: pprimes
SIZE 0 do Flags i + c@ if i 2 + . then loop cr ;

\ uncomment the following to print the primes or debug
\ pprimes
\ flags 100 dump

bye \ th-th-that's all folks!
```
sieve.ghc
```-- \$Id: sieve.ghc,v 1.4 2001/07/26 13:16:43 doug Exp \$
-- http://www.bagley.org/~doug/shootout/
-- from Roland Dowdeswell

module Main where

import System(getArgs)

main = getArgs >>= putStrLn . ("Count: "++) . show . mytest . read . headOr1
where headOr1 x = if length x /= 1 then "1" else head x

-- here we try to force it to recompute at each step.  Note
-- that we are not naming `sieve [2..8192]' and we are forcing
-- a comparison with -1.  Of course there is still no guarantee
-- that any particular Haskell implementation will actually
-- recompute the value.
mytest :: Int -> Int
mytest 1 = length (sieve [2..8192])
mytest n | length (sieve [2..8192]) == -1 = error "doh"
| otherwise                      = mytest (n-1)

-- we use Int rather than let Haskell default to Integer,
-- because we are trying to remain competetive with other
-- languages that do not do arbitrary precision math by
-- default...
sieve :: [Int] -> [Int]
sieve [] = []
sieve (h:t) = h : sieve [x| x<-t, x`mod`h /= 0]
```
sieve.gnat
```-- \$Id: sieve.gnat,v 1.0 2003/06/11 12:03:00 dada Exp \$
-- Ada 95 code by C.C.

procedure Sieve is
High        : constant := 8192;
Is_Prime    : array (2 .. High) of Boolean;
Count, K, N : Natural := 0;
begin
begin
exception
when Constraint_Error => null;
end;
for Iter in 1 .. N loop
declare
pragma Suppress (Overflow_Check);
pragma Suppress (Index_Check);
pragma Suppress (Range_Check);
begin
Count := 0;
Is_Prime := (others => True);
for J in Is_Prime'Range loop
if Is_Prime (J) then
K := J + J;
while K <= Is_Prime'Last loop
Is_Prime (K) := False;        --  K is not a prime since a
K := K + J;                   --  multiple of prime J
end loop;
Count := Count + 1;
end if;
end loop;
end;
end loop;
Text_IO.Put_Line ("Count:" & Natural'Image (Count));
end Sieve;

```
sieve.guile
```#!/usr/local/bin/guile \
-e main -s
!#

;;; \$Id: sieve.guile,v 1.8 2001/06/29 23:12:37 doug Exp \$
;;; http://www.bagley.org/~doug/shootout/
;;; with help from Benedikt Rosenau

(use-modules (ice-9 format))

(define (main args)
(let ((n (or (and (= (length args) 2) (string->;number (cadr args))) 1))
(count 0))
(while (>; n 0)
(set! n (- n 1))
(let ((flags (make-vector 8192 #t)))
(set! count 0)
(do ((i 2 (+ 1 i)))
((>;= i 8192))
(if (vector-ref flags i)
(begin
(do ((k (+ i i) (+ k i)))
((>;= k 8192))
(vector-set! flags k #f))
(set! count (+ 1 count)))))))
(display (format "Count: ~D\n" count))))
```
sieve.ici
```// \$Id: sieve.ici,v 1.0 2003/01/03 11:16:00 dada Exp \$
//
// contributed by Tim Long

n := argv[1] ? int(argv[1]) : 1;
while (n--)
{
count := 0;
flags := build(8193, "c", 1);
for (i := 2; i <= 8192; ++i)
{
if (flags[i])
{
for (k := i + i; k <= 8192; k += i)
flags[k] = 0;
++count;
}
}
}
printf("Count: %d\n", count);
```
sieve.icon
```# -*- mode: icon -*-
# \$Id: sieve.icon,v 1.3 2000/12/17 23:34:06 doug Exp \$
# http://www.bagley.org/~doug/shootout/

procedure main(argv)
n := argv[1] | 1
every i := 1 to n do count := sieve()
write("Count: ", count)
end

# algorithm from a test program that is distributed with
# the icon source

procedure sieve()
local limit, s, i
limit := 8192
s := set()
every insert(s,1 to limit)
every member(s,i := 2 to limit) do
every delete(s,i + i to limit by i)
delete(s,1)
return(*s);
end
```
sieve.java
```// \$Id: sieve.java,v 1.8 2001/05/06 04:37:45 doug Exp \$
// http://www.bagley.org/~doug/shootout/

public class sieve {
public static void main(String args[]) {
int NUM = Integer.parseInt(args[0]);
boolean [] flags = new boolean[8192 + 1];
int count = 0;
while (NUM-- > 0) {
count = 0;
for (int i=2; i <= 8192; i++) {
flags[i] = true;
}
for (int i=2; i <= 8192; i++) {
if (flags[i]) {
// remove all multiples of prime: i
for (int k=i+i; k <= 8192; k+=i) {
flags[k] = false;
}
count++;
}
}
}
System.out.print("Count: " + count + "\n");
}
}

```
sieve.jscript
```// -*- mode: java -*-
// \$Id: sieve.njs,v 1.1 2001/07/08 20:20:06 doug Exp \$
// http://www.bagley.org/~doug/shootout/
// from: David Hedbor
// modified by Aldo Calpini <dada@perl.it> for Win32

var flags, flagsorig = Array(8193);
var n, i, k, count;

ARGS = WScript.Arguments;

if(ARGS.length > 0) {
n = parseInt(ARGS.Item(0), "10");
if(n < 1) n = 1;
} else {
n = 1;
}

for (i = 2; i <= 8192; i++) {  flagsorig[i] = 1; }
while (n--) {
count = 0;
flags = flagsorig.concat();
for (i = 2; i <= 8192; i++) {
if (flags[i]) {
for (k=i+i; k <= 8192; k+=i)
flags[k] = 0;
count++;
}
}
}

WScript.Echo("Count:", count);

```
sieve.lcc
```/* -*- mode: c -*-
* \$Id: sieve.gcc,v 1.7 2001/05/06 04:37:45 doug Exp \$
* http://www.bagley.org/~doug/shootout/
*/

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

int
main(int argc, char *argv[]) {
int NUM = ((argc == 2) ? atoi(argv[1]) : 1);
static char flags[8192 + 1];
long i, k;
int count = 0;

while (NUM--) {
count = 0;
for (i=2; i <= 8192; i++) {
flags[i] = 1;
}
for (i=2; i <= 8192; i++) {
if (flags[i]) {
// remove all multiples of prime: i
for (k=i+i; k <= 8192; k+=i) {
flags[k] = 0;
}
count++;
}
}
}
printf("Count: %d\n", count);
return(0);
}

```
sieve.lua
```-- \$Id: sieve.lua,v 1.9 2001/05/06 04:37:45 doug Exp \$
-- http://www.bagley.org/~doug/shootout/
--
-- Roberto Ierusalimschy pointed out the for loop is much
-- faster for our purposes here than using a while loop.

function main(num)
local flags = {}
for num=num,1,-1 do
count = 0
for i=2,8192 do
flags[i] = 1
end
for i=2,8192 do
if flags[i] == 1 then
k = 0
for k=i+i, 8192, i do
flags[k] = 0
end
count = count + 1
end
end
end
end

NUM = tonumber((arg and arg[1])) or 1
count = 0
main(NUM)
write("Count: ", count, "\n")
```
sieve.lua5
```-- \$Id: sieve.lua,v 1.9 2001/05/06 04:37:45 doug Exp \$
-- http://www.bagley.org/~doug/shootout/
-- contributed by Roberto Ierusalimschy
--
-- Roberto Ierusalimschy pointed out the for loop is much
-- faster for our purposes here than using a while loop.

function main(num)
local flags = {}
for num=1,num do
count = 0
for i=2,8192 do
flags[i] = true
end
for i=2,8192 do
if flags[i] then
for k=i+i, 8192, i do
flags[k] = false
end
count = count + 1
end
end
end
end

NUM = tonumber((arg and arg[1])) or 1
count = 0
main(NUM)
io.write("Count: ", count, "\n")

```
sieve.mawk
```# \$Id: sieve.mawk,v 1.3 2001/05/25 03:33:08 doug Exp \$
# http://www.bagley.org/~doug/shootout/

BEGIN {
n = (ARGV[1] < 1) ? 1 : ARGV[1];
while (n--) {
count=0;
for(i=2; i <= 8192; flags[i++]=1);
for (i=2; i <= 8192; i++) {
if (flags[i]) {
# remove all multiples of prime: i
for (k=i+i; k <= 8192; k+=i) {
flags[k] = 0;
}
count++;
}
}
}
printf("Count: %d\n", count);
exit;
}
```
sieve.mercury
```% ---------------------------------------------------------------------------- %
% sieve.m
% Ralph Becket <rbeck@microsoft.com>
% Mon Jan  8 14:23:22 GMT 2001
% vim: ts=4 sw=4 et tw=0 wm=0 ff=unix
%
% Eratosthenes' Sieve - counts the number of primes in 2..8192
%
% ---------------------------------------------------------------------------- %

:- module mytest.

:- interface.

:- import_module io.

:- pred main(io__state, io__state).
:- mode main(di, uo) is cc_multi.

:- implementation.

:- import_module int, bool, array, string, list, require, benchmarking.

main -->
io__command_line_arguments(ArgV),
(   { ArgV = [],        Repeats = 1 }
;   { ArgV = [Arg],     Repeats = string__det_to_int(Arg) }
;   { ArgV = [_,_|_],   error("usage: sieve [NumIterations]") }
),
{ P = ( pred(Sz::in, N::out) is det :- N = count_primes(Sz) ) },
{ benchmarking__benchmark_det(P, 8192, Count, Repeats, Time) },
io__format("Count: %d\n", [i(Count)]).

:- func count_primes(int) = int.

count_primes(Size) = sieve_and_count(2, array__init(Size, yes), 0).

:- func sieve_and_count(int, array(bool), int) = int.
:- mode sieve_and_count(in, array_di, in) = out is det.

sieve_and_count(I, A, N) =
(      if I > array__max(A)         then N
else if array__lookup(A, I) = no  then sieve_and_count(I + 1, A, N)
else    sieve_and_count(I + 1, filter_multiples(I + I, I, A), N + 1)
).

:- func filter_multiples(int, int, array(bool)) = array(bool).
:- mode filter_multiples(in, in, array_di) = array_uo is det.

filter_multiples(I, P, A) =
( if I > array__max(A)
then A
else filter_multiples(I + P, P, array__set(A, I, no))
).
```
sieve.mingw32
```/* -*- mode: c -*-
* \$Id: sieve.gcc,v 1.7 2001/05/06 04:37:45 doug Exp \$
* http://www.bagley.org/~doug/shootout/
*/

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

int
main(int argc, char *argv[]) {
int NUM = ((argc == 2) ? atoi(argv[1]) : 1);
static char flags[8192 + 1];
long i, k;
int count = 0;

while (NUM--) {
count = 0;
for (i=2; i <= 8192; i++) {
flags[i] = 1;
}
for (i=2; i <= 8192; i++) {
if (flags[i]) {
// remove all multiples of prime: i
for (k=i+i; k <= 8192; k+=i) {
flags[k] = 0;
}
count++;
}
}
}
printf("Count: %d\n", count);
return(0);
}

```
sieve.modula2
```(* The Great Win32 Language Shootout http://dada.perl.it/shootout/

contributed by Isaac Gouy (Modula2 novice)

To build: xc =m sieve
To run:   sieve 900
*)

MODULE Sieve;
<* m2extensions + *>
<* checkindex - *>
<* coverflow - *>

(* Prefer unqualified procedures *)
FROM LanguageShootout IMPORT N;

FROM STextIO IMPORT WriteString, WriteLn;
FROM SWholeIO IMPORT WriteCard;

CONST
start = 2;
stop = 8192;

TYPE Boolean_Array = ARRAY [start..stop] OF BOOLEAN;

VAR
array_size: CARDINAL;
n, count, i, k: CARDINAL;

BEGIN
n := N();
array_size := SIZE(Boolean_Array);

WHILE n > 0 DO
DEC(n);
count := 0;

(* Set all the isPrimeNumber array to TRUE *)

FOR i := start TO stop DO
INC(count);
k := i+i;
WHILE k <= stop DO
INC(k, i);
END;
END;
END;
END;

WriteString("Count:"); WriteCard(count,0); WriteLn;
END Sieve.```
sieve.nice
```/* The Great Win32 Language Shootout http://dada.perl.it/shootout/
contributed by Isaac Gouy (Nice novice)

To compile:
nicec --sourcepath=.. -d=. -a sieve.jar sieve

To run:
java -jar sieve.jar 900
*/

// NOTE: the type of constants & variables declared with
//       let & var will be inferred by the compiler

import ackermann; // reuse toSingleInt

void main(String[] args){
var n = toSingleInt(args);

let start = 2;
let stop = 8192;
var isPrime = new boolean[stop+1];
var count = 0;

while (n-- > 0){
count = 0;
for(var i=start; i <= stop; i++) isPrime[i] = true;
for(var i=start; i <= stop; i++)
if(isPrime[i]) {
// remove all multiples of prime: i
for(var k=i+i; k <= stop; k+=i) isPrime[k] = false;
count++;
}
}
println("Count: " + count);
}```
sieve.ocaml
```(*
* \$Id: sieve.ocaml,v 1.10 2001/06/10 04:12:44 doug Exp \$
* http://www.bagley.org/~doug/shootout/
* based on code from Markus Mottl
*)

let flags = String.make 8193 'f'

let rec inner_loop k i =
if k < 8193 then begin
flags.[k] <- 'f';
inner_loop (k + i) i
end

let rec middle_loop i cnt =
if i < 8193 then
if flags.[i] = 't' then begin
inner_loop (i + i) i;
middle_loop (i + 1) (cnt + 1) end
else middle_loop (i + 1) cnt
else cnt

let _ =
let num =
try int_of_string Sys.argv.(1)
with Invalid_argument _ -> 1
and cnt = ref 0 in
for iter = 1 to num do
for i = 2 to 8192 do flags.[i] <- 't' done;
cnt := middle_loop 2 0;
done;
Printf.printf "Count: %d\n" !cnt
```
sieve.ocamlb
```(*
* \$Id: sieve.ocaml,v 1.10 2001/06/10 04:12:44 doug Exp \$
* http://www.bagley.org/~doug/shootout/
* based on code from Markus Mottl
*)

let flags = String.make 8193 'f'

let rec inner_loop k i =
if k < 8193 then begin
flags.[k] <- 'f';
inner_loop (k + i) i
end

let rec middle_loop i cnt =
if i < 8193 then
if flags.[i] = 't' then begin
inner_loop (i + i) i;
middle_loop (i + 1) (cnt + 1) end
else middle_loop (i + 1) cnt
else cnt

let _ =
let num =
try int_of_string Sys.argv.(1)
with Invalid_argument _ -> 1
and cnt = ref 0 in
for iter = 1 to num do
for i = 2 to 8192 do flags.[i] <- 't' done;
cnt := middle_loop 2 0;
done;
Printf.printf "Count: %d\n" !cnt
```
sieve.oz
```%%% \$Id: sieve.oz,v 1.1 2002/08/19 16:33:00 dada Exp \$

%%%
%%% contributed by Isaac Gouy

%%  Usage: start from command line with
%%     ozc -x sieve.oz -o sieve.oz.exe
%%     sieve.oz.exe 900

functor
import System Application

define Args N Flags Start Stop in

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

Start = 2
Stop = 8192

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

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

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

{Application.exit 0}
end
```
sieve.parrot
```
set I0, P0[1]
new P1, .Array
set P1, 8193

N_LOOP:        unless I0, N_DONE
set I1, 0

set I2, 0
INIT_ARRAY:    set P1[I2], 1
inc I2
lt I2, 8192, INIT_ARRAY

set I2, 2
I_LOOP:        ge I2, 8192, I_DONE
set I4, P1[I2]
unless I4, I_NEXT

set I3, I2
J_LOOP:        ge I3, 8192, J_DONE
set P1[I3], 0
branch J_LOOP
J_DONE:        inc I1

I_NEXT:        inc I2
branch I_LOOP

I_DONE:        dec I0
branch N_LOOP

N_DONE:        print "Count: "
print I1
print "\n"
end

```
sieve.perl
```#!/usr/local/bin/perl
# \$Id: sieve.perl,v 1.10 2001/05/06 04:37:45 doug Exp \$
# http://www.bagley.org/~doug/shootout/

use strict;
use integer;

# Tony Bowden suggested using 0..8192 to create the array
# and to test for defined instead of the value.

my \$NUM = \$ARGV[0];
\$NUM = 1 if (\$NUM < 1);
my \$count;
my @flags = ();
while (\$NUM--) {
\$count = 0;
my @flags = (0 .. 8192);
for my \$i (2 .. 8192 ) {
next unless defined \$flags[\$i];
# remove all multiples of prime: i
for (my \$k=\$i+\$i; \$k <= 8192; \$k+=\$i) {
undef \$flags[\$k];
}
\$count++;
}
}
print "Count: \$count\n";
```
sieve.php
```<?php
/*
\$Id: sieve.php,v 1.1 2001/05/06 04:37:37 doug Exp \$
http://www.bagley.org/~doug/shootout/
*/
\$n = (\$argc == 2) ? \$argv[1] : 1;
\$count = 0;
while (\$n-- > 0) {
\$count = 0;
\$flags = range (0,8192);
for (\$i=2; \$i<8193; \$i++) {
if (\$flags[\$i] > 0) {
for (\$k=\$i+\$i; \$k <= 8192; \$k+=\$i) {
\$flags[\$k] = 0;
}
\$count++;
}
}
}
print "Count: \$count\n";
?>
```
sieve.pike
```#!/usr/local/bin/pike// -*- mode: pike -*-
// \$Id: sieve.pike,v 1.9 2001/05/06 04:37:45 doug Exp \$
// http://www.bagley.org/~doug/shootout/
// from: Per Hedbor

void main(int argc, array(string) argv)
{
array(int) flags;
int i, k, count, num;

num = (int)argv[-1];
if (num < 1)
num = 1;

while (num--) {
count = 0;
flags = ({ 1 })*8193;
for (i=2; i <= 8192; i++) {
if (flags[i]) {
for (k=i+i; k <= 8192; k+=i)
flags[k] = 0;
count++;
}
}
}
write("Count: %d\n", count);
}
```
sieve.pliant
```# \$Id: sieve.pliant,v 1.0 2002/02/06 15:17:00 dada Exp \$

module "/pliant/language/context.pli"

gvar Array:Int flags
gvar Int count
gvar Int i
gvar Int k
gvar Str s_n := cast ((pliant_script_args translate Address 1) map CStr) Str
if (s_n parse (gvar Int n))
flags:size := 8192
while n > 0
count := 0
for (i) 0 (flags:size)
flags:i := 1
for (i) 2 8192
if flags:i = 1
for k i+i 8192 step i
flags:k := 0
count := count + 1
n := n - 1
console "Count: " count eol
else
console "usage: nestedloop.pli <number>" eol
```
sieve.poplisp
```;;; -*- mode: lisp -*-
;;; \$Id: sieve.poplisp,v 1.0 2002/05/03 12:12:00 dada Exp \$

(declaim (optimize (speed 3) (safety 0) (debug 0) (space 0) (compilation-speed 0)))
(let ((n (parse-integer (or (car pop11::poparglist) "1")))
(flags (make-array 8193 :element-type 'fixnum :initial-element 1)))
(loop repeat n of-type fixnum for count of-type fixnum = 0 then 0 do
(loop for i fixnum from 2 upto 8192 do
(unless (zerop (aref flags i))
(loop for k fixnum from (* 2 i) upto 8192 by i do
(setf (aref flags k) 0))
(incf count)))
finally (format t "Count: ~D~%" count)))
```
sieve.python
```#!/usr/local/bin/python
# \$Id: sieve.python,v 1.10 2001/05/06 04:37:45 doug Exp \$
# http://www.bagley.org/~doug/shootout/
# with help from Brad Knotwell

import sys

def main():
NUM = int(sys.argv[1])
for foo in xrange(0,NUM):
flags = (8192+1) * [1]
count = 0
for i in xrange(2,8192+1):
if flags[i]:
# remove all multiples of prime: i
k = i + i
while k <= 8192:
flags[k] = 0
k = k + i
count = count + 1
print "Count:", count

main()
```
sieve.rebol
```REBOL [
Title:   "Sieve of Erathostenes"
Author:  "Aldo Calpini"
Date:    03-Jul-2001
File:    %sieve.r
]

NUM: to-integer to-string system/script/args
NUM: either NUM < 1 [ 1 ] [ NUM ]

while [ NUM > 0 ] [
count: 0
comment [
flags: array/initial 1 8192
]

flags: copy []
for i 0 8192 1 [
insert tail flags 1
]

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

write %output.rebol rejoin [ "Count: " count ]
```
sieve.rexx
```parse arg n
If n < 1 Then Do
n = 1
End

Do While n > 0
count = 0
Do j = 0 To 8192
flags.j = 1
End
Do i = 2 To 8192
If flags.i <> 0 Then Do
Do k = i+i To 8192 By i
flags.k = 0
End
count = count + 1
End
End
n = n - 1
End

say "Count: "count
```
sieve.ruby
```#!/usr/local/bin/ruby
# -*- mode: ruby -*-
# \$Id: sieve.ruby,v 1.12 2001/05/06 04:37:45 doug Exp \$
# http://www.bagley.org/~doug/shootout/

NUM = Integer(ARGV.shift || 1)

count = i = j = 0
flags0 = Array.new(8192,1)

NUM.times do
count = 0
flags = flags0.dup
for i in 2 .. 8192
next unless flags[i]
# remove all multiples of prime: i
(i*i).step(8192, i) do |j|
flags[j] = nil
end
count = count + 1
end
end

print "Count: ", count, "\n"

```
sieve.se
```-- -*- mode: eiffel -*-
-- \$Id: sieve.se,v 1.4 2001/06/10 04:23:34 doug Exp \$
-- http://www.bagley.org/~doug/shootout/

class SIEVE

creation make

feature

make is

local
count: INTEGER;
flags: ARRAY[CHARACTER];
i: INTEGER;
num: INTEGER;
j: INTEGER;
k: INTEGER;
do
if argument_count = 1 then
num := argument(1).to_integer
else
num := 1
end

!!flags.make(0, 8193)

from
j := 0
until
j = num
loop

count := 0

from
i := 2
until
i > 8192
loop
flags.put('t', i)
i := i + 1
end

from
i := 2
until
i > 8192
loop
if flags.item(i) = 't' then
from
k := i + i
until
k > 8192
loop
flags.put('f', k)
k := k + i
end
count := count + 1
end
i := i + 1
end

j := j + 1
end

std_output.put_string("Count: ")
std_output.put_integer(count)
std_output.put_character('%N')
end;

end
```
sieve.slang
```% \$Id: sieve.slang,v 1.0 2003/01/03 12:51:00 dada Exp \$
%
% contributed by John E. Davis

define main()
{
variable NUM = integer (__argv[1]);
variable flags = Int_Type[8192 + 1];
loop (NUM)
{
flags[*] = 1;
variable count = 0;
_for (2, 8192, 1)
{
variable i = ();
if (flags[i])
{
#iftrue
flags[[i+i:8192:i]] = 0;
#else
_for (i+i, 8192, i)
{
variable j = ();
flags[j] = 0;
}
#endif
count++;
}
}
}

vmessage ("Count: %d", count);
}
main();
```
sieve.smlnj
```(* -*- mode: sml -*-
* \$Id: sieve.smlnj,v 1.8 2001/08/20 01:11:11 doug Exp \$
* http://www.bagley.org/~doug/shootout/
* with help from Dan Wang
*)

structure Test : sig
val main : (string * string list) -> OS.Process.status
end = struct
structure WA = Word8Array
val flags  = WA.array (8193, 0w0)

fun init() = let
fun loop i =
if i < 8193 then (WA.update(flags,i,0w1);loop(i+1))
else ()
in loop 2
end

fun do_elts(i,count) =
if i < 8193 then
if WA.sub(flags,i) = 0w1 then let
fun loop k =
if k < 8193 then (WA.update(flags,k,0w0);loop(k+i))
else ()
in loop (i + i) ; do_elts(i + 1,count + 1)
end
else do_elts(i + 1, count)
else count

fun repeat 0 = (init (); do_elts(2,0))
| repeat n = (init (); do_elts(2,0);repeat(n-1))

fun printl [] = print "\n" | printl(h::t) = ( print h ; printl t )
fun atoi s = case Int.fromString s of SOME num => num | NONE => 0

fun main(name, param_list) =  let
val arg = hd(param_list @ ["1"]);
val num = atoi arg
val count = repeat num
in  printl ["Count: ", Int.toString count];
OS.Process.success
end
end

val _ = SMLofNJ.exportFn("sieve", Test.main);
```
sieve.tcl
```#!/usr/local/bin/tclsh
# \$Id: sieve.tcl,v 1.9 2001/05/06 04:37:45 doug Exp \$
# http://www.bagley.org/~doug/shootout/
# with help from: Kristoffer Lawson

proc sieve {num} {
while {\$num > 0} {
incr num -1
set count 0
for {set i 2} {\$i <= 8192} {incr i 1} {
set flags(\$i) 1
}
for {set i 2} {\$i <= 8192} {incr i 1} {
if {\$flags(\$i) == 1} {
# remove all multiples of prime: i
for {set k [expr {\$i+\$i}]} {\$k <= 8192} {incr k \$i} {
set flags(\$k) 0
}
incr count 1
}
}
}
return \$count
}

set NUM [lindex \$argv 0]
if {\$NUM < 1} {
set NUM 1
}

set count [sieve \$NUM]
puts "Count: \$count"
```
sieve.vbscript
```NUM = WScript.Arguments(0)
If NUM < 1 Then NUM = 1
Dim Flags(8192)
count = 0

While NUM > 0
NUM = NUM - 1
count = 0
For A = 0 To 8192
Flags(A) = A
Next
For I = 2 To 8192
If Flags(I) <> -1 Then
For K = I+I To 8192 Step I
Flags(K) = -1
Next
Count = Count + 1
End If
Next
Wend
WScript.Echo "Count: " & Count
```
sieve.vc
```/* -*- mode: c -*-
* \$Id: sieve.gcc,v 1.7 2001/05/06 04:37:45 doug Exp \$
* http://www.bagley.org/~doug/shootout/
*/

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

int
main(int argc, char *argv[]) {
int NUM = ((argc == 2) ? atoi(argv[1]) : 1);
static char flags[8192 + 1];
long i, k;
int count = 0;

while (NUM--) {
count = 0;
for (i=2; i <= 8192; i++) {
flags[i] = 1;
}
for (i=2; i <= 8192; i++) {
if (flags[i]) {
// remove all multiples of prime: i
for (k=i+i; k <= 8192; k+=i) {
flags[k] = 0;
}
count++;
}
}
}
printf("Count: %d\n", count);
return(0);
}

```
sieve.vc++
```// -*- mode: c++ -*-
// \$Id: sieve.g++,v 1.5 2001/06/20 03:20:03 doug Exp \$
// http://www.bagley.org/~doug/shootout/
// From Bill Lear

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdlib>

using namespace std;

int main(int argc, char *argv[]) {
size_t NUM = (argc == 2 ? (atoi(argv[1]) < 1 ? 1 : atoi(argv[1])): 1);

vector<char> primes(8192 + 1);
vector<char>::iterator pbegin = primes.begin();
vector<char>::iterator begin = pbegin + 2;
vector<char>::iterator end = primes.end();

while (NUM--) {
fill(begin, end, 1);
for (vector<char>::iterator i = begin; i != end; ++i) {
if (*i) {
const size_t p = i - pbegin;
for (vector<char>::iterator k = i + p; k <= end; k += p) {
*k = 0;
}
}
}
}

cout << "Count: " << count(begin, end, 1) << endl;
}
```
sieve.vpascal
```program sieve;
uses SysUtils;

var
NUM, i, k, count : integer;
flags : array[0..8192] of integer;

begin
if ParamCount = 0 then
NUM := 1
else
NUM := StrToInt(ParamStr(1));

if NUM < 1 then NUM := 1;

while NUM > 0 do
begin
Dec(NUM);
count := 0;
for i := 0 to 8192 do
begin
flags[i] := i;
end;
for i := 2 to 8192 do
begin
if flags[i] <> -1 then
begin
k := i+i;
while k <= 8192 do
begin
flags[k] := -1;
Inc(k, i);
end;
Inc(count);
end;
end;
end;
WriteLn('Count: ' + IntToStr(Count));
end.
```