links

< home >
< unix stuff >
< code >
< writing >
< archive >
< music >
< photos >
< recipes >
< site map >
< about badcomputer >

The sieve of eratosthenes

Ada

-- Sieve of Eratosthenes in Ada
-- Written by Rob Hoelz

with Ada.Text_IO, Ada.Integer_Text_IO, Ada.Command_Line;
use Ada.Text_IO, Ada.Integer_Text_IO, Ada.Command_Line;

procedure Sieve is
    type List is array (Integer range <>) of Boolean;
    type List_Pointer is access List;

    Limit : Integer;
    Primes : List_Pointer;

procedure RemoveMultiples(Primes : in out List_Pointer; Base : in Integer) is
    i : Integer := Base * 2;
begin
    while i <= Primes'Last loop
        if i mod Base = 0 then
            Primes(i) := false;
        end if;
        i := i + Base;
    end loop;
end RemoveMultiples;

function NextPrime(Primes : in List_Pointer; CurrPrime : in Integer) return Integer is
begin
    for i in (CurrPrime + 1) .. Primes'Last loop
        if Primes(i) then
            return i;
        end if;
    end loop;
    return Primes'Last;
end NextPrime;

procedure GeneratePrimes(Primes : in out List_Pointer) is
    CurrPrime : Integer := 2;
begin
    while (CurrPrime * CurrPrime) <= Primes'Last loop
        RemoveMultiples(Primes, CurrPrime);
        CurrPrime := NextPrime(Primes, CurrPrime);
    end loop;
end GeneratePrimes;

begin
    if Argument_Count > 0 then
        Limit := Integer'Value(Argument(1));
        Primes := new List (2..Limit);

        for i in Primes'Range loop
            Primes(i) := true;
        end loop;

        generatePrimes(Primes);
        for i in Primes'Range loop
            if Primes(i) then
                Put(i, 0);
                Put(" ");
            end if;
        end loop;
    end if;
end Sieve;

back to Eratosthenes page

stats

It is Friday December 05, 2008 10:20 am
This page served 993 times
This page last modified: April 14, 2008 11:28 am
Your IP address is: 38.103.63.61
You are browsing using: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)
You are browsing from: United States.
badcomputer.org's uptime: 10:20:37 up 24 days, 14:30, 2 users, load average: 0.02, 0.02, 0.00