#!/bin/bash
# sieve.sh (ex68.sh)

# Crible d'Ératosthene
# Ancien algorithme pour trouver les nombres premiers.

# Ceci s'exécute bien moins rapidement que le programme équivalent écrit en C.

LIMITE_BASSE=1       # Commençant avec 1.
LIMITE_HAUTE=1000    # Jusqu'à 1000.
# (Vous pouvez augmenter cette valeur...  si vous avez du temps devant vous.)

PREMIER=1
NON_PREMIER=0

let DIVISE=LIMITE_HAUTE/2
# Optimisation :
# Nécessaire pour tester les nombres à mi-chemin de la limite supérieure (pourquoi ?).


declare -a Premiers
# Premiers[] est un tableau.


initialise ()
{
# Initialise le tableau.

i=$LIMITE_BASSE
until [ "$i" -gt "$LIMITE_HAUTE" ]
do
  Premiers[i]=$PREMIER
  let "i += 1"
done
# Assume que tous les membres du tableau sont coupables (premiers) avant d'être
# reconnus innocent.
}

affiche_premiers ()
{
# Affiche les membres du tableau Premiers[] indiqués comme premiers.

i=$LIMITE_BASSE

until [ "$i" -gt "$LIMITE_HAUTE" ]
do

  if [ "${Premiers[i]}" -eq "$PREMIER" ]
  then
    printf "%8d" $i
    # 8 espaces par nombre rend l'affichage joli, avec colonne.
  fi
  
  let "i += 1"
  
done

}

examine () # Examine minutieusement les non premiers.
{

let i=$LIMITE_BASSE+1
# Nous savons que 1 est premier, donc commençons avec 2.

until [ "$i" -gt "$LIMITE_HAUTE" ]
do

if [ "${Premiers[i]}" -eq "$PREMIER" ]
#  Ne nous embêtons pas à examiner les nombres déjà examinés (indiqués comme
#+ non premiers).
then

  t=$i

  while [ "$t" -le "$LIMITE_HAUTE" ]
  do
    let "t += $i "
    Premiers[t]=$NON_PREMIER
    # Indiqué comme non premier tous les multiples.
  done

fi  

  let "i += 1"
done  


}


# =========================================================
# main ()
# Appeler les fonctions séquentiellement.
initialise
examine
affiche_premiers
# C'est ce qu'ils appelent de la programmation structurée.
# =========================================================

echo

exit 0



# --------------------------------------------------------------------------- #
# Le code ci-dessous ne sera pas exécuté à cause du exit ci-dessus.

# Cette version améliorée de Sieve, par Stephane Chazelas,
# s'exécute un peu plus rapidement.

# Doit être appelé avec un argument en ligne de commande (limite des premiers).

LIMITE_HAUTE=$1                   # À partir de la ligne de commande.
let DIVISE=LIMITE_HAUTE/2         # Mi-chemin du nombre max.

Premiers=( '' $(seq $LIMITE_HAUTE) )

i=1
until (( ( i += 1 ) > DIVISE ))  # A besoin de vérifier à mi-chemin.
do
  if [[ -n $Premiers[i] ]]
  then
    t=$i
    until (( ( t += i ) > LIMITE_HAUTE ))
    do
      Premiers[t]=
    done
  fi  
done  
echo ${Premiers[*]}

exit $?
