#!/bin/bash
# sieve.sh (ex68.sh)
# Sieve of Eratosthenes
# Ancient algorithm for finding prime numbers.
# This runs a couple of orders of magnitude slower
#+ than the equivalent program written in C.
LOWER_LIMIT=1 # Starting with 1.
UPPER_LIMIT=1000 # Up to 1000.
# (You may set this higher . . . if you have time on your hands.)
PRIME=1
NON_PRIME=0
let SPLIT=UPPER_LIMIT/2
# Optimization:
# Need to test numbers only halfway to upper limit (why?).
declare -a Primes
# Primes[] is an array.
initialize ()
{
# Initialize the array.
i=$LOWER_LIMIT
until [ "$i" -gt "$UPPER_LIMIT" ]
do
Primes[i]=$PRIME
let "i += 1"
done
# Assume all array members guilty (prime)
#+ until proven innocent.
}
print_primes ()
{
# Print out the members of the Primes[] array tagged as prime.
i=$LOWER_LIMIT
until [ "$i" -gt "$UPPER_LIMIT" ]
do
if [ "${Primes[i]}" -eq "$PRIME" ]
then
printf "%8d" $i
# 8 spaces per number gives nice, even columns.
fi
let "i += 1"
done
}
sift () # Sift out the non-primes.
{
let i=$LOWER_LIMIT+1
# We know 1 is prime, so let's start with 2.
until [ "$i" -gt "$UPPER_LIMIT" ]
do
if [ "${Primes[i]}" -eq "$PRIME" ]
# Don't bother sieving numbers already sieved (tagged as non-prime).
then
t=$i
while [ "$t" -le "$UPPER_LIMIT" ]
do
let "t += $i "
Primes[t]=$NON_PRIME
# Tag as non-prime all multiples.
done
fi
let "i += 1"
done
}
# ==============================================
# main ()
# Invoke the functions sequentially.
initialize
sift
print_primes
# This is what they call structured programming.
# ==============================================
echo
exit 0
# -------------------------------------------------------- #
# Code below line will not execute, because of 'exit.'
# This improved version of the Sieve, by Stephane Chazelas,
#+ executes somewhat faster.
# Must invoke with command-line argument (limit of primes).
UPPER_LIMIT=$1 # From command line.
let SPLIT=UPPER_LIMIT/2 # Halfway to max number.
Primes=( '' $(seq $UPPER_LIMIT) )
i=1
until (( ( i += 1 ) > SPLIT )) # Need check only halfway.
do
if [[ -n $Primes[i] ]]
then
t=$i
until (( ( t += i ) > UPPER_LIMIT ))
do
Primes[t]=
done
fi
done
echo ${Primes[*]}
exit 0