links

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

sieve of eratosthenes

Bash

#!/bin/bash

# Sieve of Eratosthenes in Bash
# Written by Rob Hoelz

removeMultiples () {
    local i=`expr $currPrime + $currPrime`
    while (( $i <= $limit )); do
        primes[$i]=0
        i=`expr $i + $currPrime`
    done
}

nextPrime () {
    currPrime=`expr $currPrime + 1`
    while (( $currPrime <= $limit )); do
        if [ ${primes[$currPrime]} -eq 1 ]
        then
            break
        fi
        currPrime=`expr $currPrime + 1`
    done
}

printList () {
    local i=0
    while (( $i <= $limit )); do
        if [ ${primes[$i]} -eq 1 ]
        then
            echo -n "$i "
        fi
        i=`expr $i + 1`
    done
    echo ''
}

if [ -z "$1" ]
then
    exit
fi

limit=$1

primes=(`yes 1 | head -$(expr $limit + 1)`)
primes[0]=0
primes[1]=0
currPrime=2

while (( `expr $currPrime \* $currPrime` <= "$limit" )); do
    removeMultiples
    nextPrime
done

printList

back to Eratosthenes page

stats

It is Saturday May 17, 2008 10:52 am
This page served 588 times
This page last modified: April 14, 2008 11:28 am
Your IP address is: 38.103.63.17
You are browsing using: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)
You are browsing from: United States.
badcomputer.org's uptime: 10:52:43 up 23 days, 11:34, 0 users, load average: 0.00, 0.00, 0.00