mirror of https://github.com/tLDP/LDP
37 lines
1.1 KiB
Bash
37 lines
1.1 KiB
Bash
#!/bin/bash
|
|
# Optimized Sieve of Eratosthenes
|
|
# Script by Jared Martin, with very minor changes by ABS Guide author.
|
|
# Used in ABS Guide with permission (thanks!).
|
|
|
|
# Based on script in Advanced Bash Scripting Guide.
|
|
# http://tldp.org/LDP/abs/html/arrays.html#PRIMES0 (ex68.sh).
|
|
|
|
# http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf (reference)
|
|
# Check results against http://primes.utm.edu/lists/small/1000.txt
|
|
|
|
# Necessary but not sufficient would be, e.g.,
|
|
# (($(sieve 7919 | wc -w) == 1000)) && echo "7919 is the 1000th prime"
|
|
|
|
UPPER_LIMIT=${1:?"Need an upper limit of primes to search."}
|
|
|
|
Primes=( '' $(seq ${UPPER_LIMIT}) )
|
|
|
|
typeset -i i t
|
|
Primes[i=1]='' # 1 is not a prime.
|
|
until (( ( i += 1 ) > (${UPPER_LIMIT}/i) )) # Need check only ith-way.
|
|
do # Why?
|
|
if ((${Primes[t=i*(i-1), i]}))
|
|
# Obscure, but instructive, use of arithmetic expansion in subscript.
|
|
then
|
|
until (( ( t += i ) > ${UPPER_LIMIT} ))
|
|
do Primes[t]=; done
|
|
fi
|
|
done
|
|
|
|
# echo ${Primes[*]}
|
|
echo # Change to original script for pretty-printing (80-col. display).
|
|
printf "%8d" ${Primes[*]}
|
|
echo; echo
|
|
|
|
exit $?
|