1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134
|
#!/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
# 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 $?
|