Skip to content

Instantly share code, notes, and snippets.

@nvanderw
Last active October 15, 2022 04:54
Show Gist options
  • Save nvanderw/1851788b45286fa0fb880c08141d217d to your computer and use it in GitHub Desktop.
Save nvanderw/1851788b45286fa0fb880c08141d217d to your computer and use it in GitHub Desktop.
bash sieve of eratosthenes
FROM alpine:latest
RUN ["apk", "add", "bash"]
COPY "sieve.sh" "$WORKDIR"
ENTRYPOINT ["./sieve.sh"]
#!/usr/bin/env bash
eratosthenes() {
tmp_dir="$1"
n="$2"
# Only need to search composites up to sqrt(n)
local max
max=$(echo "sqrt($n)" | bc)
# Use files in $tmp_dir to represent a set of composites (starts empty)
local i
local j
seq 2 "$max" | while IFS= read -r i; do
if [ -e "$tmp_dir/$i" ]; then
continue
fi
seq $(( i * i )) "$i" "$n" | while IFS= read -r j; do
touch "$tmp_dir/$j"
done
done
seq 2 "$n" | while IFS= read -r i; do
if ! [ -e "$tmp_dir/$i" ]; then
echo "$i"
fi
done
}
set -uo pipefail
if [ "$#" -lt 1 ]; then
echo "Usage: $0 N"
exit 1
fi
N="$1"
TMP_DIR=$(mktemp -d)
# Clean up the temp dir when done
trap 'rm -Rf $TMP_DIR' EXIT
eratosthenes "$TMP_DIR" "$N"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment