links

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

The sieve of eratosthenes

Pascal

(* Sieve of Eratosthenes in Pascal
 * Written by Rob Hoelz
 *)

program sieve(output);

var
    limit : longint;
    primes : ^boolean;

(* I didn't know of a standard library atoi... *)
function atoi(s : string) : longint;
var i : longint;
var num : longint;
begin
    num := 0;
    i := 0;

    for i := 1 to length(s) do
    begin
        num := num * 10;
        num := num + (ord(s[i]) - ord('0'));
    end;
    atoi := num
end;

procedure removeMultiples(base : longint);
var i : longint;
begin
    i := base + base;
    while i <= limit do
    begin
        primes[i] := false;
        i := i + base
    end
end;

function nextPrime(currPrime : longint) : longint;
var i : longint;
begin

    for i := currPrime + 1 to limit do
    begin
        if primes[i] then
            break
    end;
    nextPrime := i
end;

procedure generatePrimes();
var currPrime : longint;
begin

    primes[1] := false;
    for currPrime := 2 to limit do
    begin
        primes[currPrime] := true;
    end;

    currPrime := 2;

    while ((currPrime * currPrime) <= limit) do
    begin
        removeMultiples(currPrime);
        currPrime := nextPrime(currPrime)
    end
end;

procedure printPrimes();
var i : longint;
begin
    for i := 1 to limit do
    begin
        if primes[i] then
        begin
            write(i);
            write(' ')
        end
    end;
    writeln()
end;

begin
    if paramcount > 0 then
    begin
        limit := atoi(paramstr(1));
        getmem(primes, limit * sizeof(boolean));
        generatePrimes();
        printPrimes();
        freemem(primes)
    end
end.

back to Eratosthenes page

stats

It is Friday December 05, 2008 10:49 am
This page served 978 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:49:51 up 24 days, 15:00, 2 users, load average: 0.00, 0.00, 0.00