Script Shell crible d'Eratosthène

Le crible d’Eratosthène

#!/bin/bash

# argument : limite supérieure pour la recherche de nombres entiers.

# POSIX compliant

# Check si on a 1 arg

[ $# -ne 1 ] && echo 'Need 1 arg' >&2 && exit 1

# Check si l'argument est un nombre entier

if ! [ "$1" -eq "$1" ] 2>/dev/null; then

    echo 'Argument must be an integer' >&2

    exit 1

fi

t="$(which bc)"

[ -z "$t" ] && echo "Error: 'bc' is not installed. Run apt-get install -y bc" >&2 && exit 1

upper_limit=$1           # argument du script, la limite supérieure

let split=$(( $(bc <<< "scale=0; sqrt($1)") + 1 ))

# On utilise bc pour calculer la racine carrée de la limite

primes=( '' $(seq $upper_limit) )

i=1

# On ajoute un compteur car un ne supprime pas de case dans le tableau, on les définit à ''...

# -2 car première case == '' et 2eme case == 1

# Ce compteur est utilisé pour la mesure du temps d'exécution. On affiche juste le nombre de résultats

# et pas des milliers de nombres premiers.

nb_primes=$((${#primes[*]} - 2))

while [ $((i += 1)) -le $split ]; do

# Optimisation du crible : la recherche s’effectue sur la racine carrée de l’intervalle initial.

  if [ -n "${primes[i]}" ]; then

    t=$i

    while [ $((t += i)) -le $upper_limit ]; do

      [ -n "${primes[t]}" ] && nb_primes=$((nb_primes - 1))

      primes[t]=

    done

  fi

done

# On "supprime" la 2eme case du tableau, car primes[1] == 1

primes[1]=

echo ${primes[*]}

echo "nb de resultats: $nb_primes"

exit $?

...