mirror of https://github.com/tLDP/LDP
135 lines
2.2 KiB
Bash
135 lines
2.2 KiB
Bash
#!/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 $?
|