# $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;
}

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

\ $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
\ array has address range: fromaddr toaddr
\ 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
    drop \ your pants!
    ;
\ 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!

// $Id: sieve.csharp,v 1.0 2002/02/14 14:02:00 dada Exp $
// http://dada.perl.it/shootout/

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

#!/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";

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.

// $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);

%%% -*- 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)].

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.

# $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;
}

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

\ $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
\ array has address range: fromaddr toaddr
\ 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
    drop \ your pants!
    ;
\ 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!

-- $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]

-- $Id: sieve.gnat,v 1.0 2003/06/11 12:03:00 dada Exp $
-- http://dada.perl.it/shootout/
-- Ada 95 code by C.C.

with Text_IO, Ada.Command_Line;

procedure Sieve is
   High        : constant := 8192;
   Is_Prime    : array (2 .. High) of Boolean;
   Count, K, N : Natural := 0;
begin
   begin
      N := Natural'Value (Ada.Command_Line.Argument (1));
   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;

#!/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))))

// $Id: sieve.ici,v 1.0 2003/01/03 11:16:00 dada Exp $
// http://dada.perl.it/shootout
//
// 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);

# -*- 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

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

// -*- 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);

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

-- $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")

-- $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")

# $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.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))
    ).

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

(* 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;
FROM SYSTEM IMPORT ADR, FILL;


CONST
   start = 2;
   stop = 8192;

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

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

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

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

      (* Set all the isPrimeNumber array to TRUE *)
      FILL( ADR(isPrimeNumber), TRUE, array_size );

      FOR i := start TO stop DO
         IF isPrimeNumber[i] THEN
	    INC(count);
            k := i+i;
            WHILE k <= stop DO
               isPrimeNumber[k] := FALSE;
	       INC(k, i);
            END;
         END;
      END;
   END;  	

   WriteString("Count:"); WriteCard(count,0); WriteLn;
END Sieve.

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

(*
 * $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

(*
 * $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

%%% $Id: sieve.oz,v 1.1 2002/08/19 16:33:00 dada Exp $
%%% http://dada.perl.it/shootout/

%%% 
%%% 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

            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
            add I3, I2
J_LOOP:        ge I3, 8192, J_DONE
            set P1[I3], 0
            add I3, I2
            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

#!/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";

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

#!/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);
}

# $Id: sieve.pliant,v 1.0 2002/02/06 15:17:00 dada Exp $
# http://dada.perl.it/shootout/

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

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

#!/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()

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
    ]
    flags: head flags

    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 ]

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

#!/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"

-- -*- 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

% $Id: sieve.slang,v 1.0 2003/01/03 12:51:00 dada Exp $
% http://dada.perl.it/shootout/
%
% 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();

(* -*- 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);

#!/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"

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

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

// -*- 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;
}

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.