bruno

Membre

script recherche nombres premiers

Salut,
codage récréatif, un script bash pour la recherche de nombres premiers.
il contient 3 fonctions  'recherche'  qui font la même chose.
la finale, une autre identique plus lisible et commentée, une autre non optimisée
avec tentative d' explication.

[== Indéfini ==]
#!/bin/bash
#
# Recherche de nombres premiers
#
##

# Un nombre est attendu en argument.
case $1 in
    *[!0-9]*|"") echo " Entrez un nombre en argument."; exit 1 ;;
esac

# Variables
maxi=$1
premiers=( '' '' $(seq 2 ${maxi}) )

Recherche_finale (){

    local c d i

    for ((i=2; i <= maxi/i; i++)); do

        ((premiers[c=i**2, d=i>2?i+i:i, i])) &&
            {
                for ((c; c <= maxi; c+=d)); do
                    premiers[c]=
                done
            }
    done
}

Recherche_optimisee (){ # même que ci-dessus en plus lisible et commentée

    local c d i

    for ((i=2; i <= maxi/i; i++)); do
        #echo "i = $i"

        if ((premiers[i])); then    # Vérifie si la valeur n'est pas déjà supprimée

            c=$((i**2))             # Carré de la valeur pour optimiser

            d=$(( i>2?i+i:i ))      # si 2, on ne double pas, supprimera tous les pairs
                                    # si > à 2, on double pour optimiser

            for((c; c <= maxi; c+=d)); do # Supprime. On commence au carré et ajoute la valeur de d
                #echo "n = ${premiers[c]}"
                premiers[c]=
            done
        fi
    done
}

Recherche_sans_optimisation () {

    local i n

    for ((i=2; i <= maxi/i; i++)); do
        echo "i = $i" # Valeur des nombres parcourus

        if ((${premiers[i]})); then

            n=i

            until (( (n += i) > maxi )); do
                echo "n = ${premiers[n]}" # Valeur à supprimer, si déja
                                            # vide, on supprime pour rien.
                premiers[n]=
            done
        fi
    done
    # Avec le second echo 'n', on peut voir qu'entre la valeur 'i' et son carré,
    # toutes sont déjà supprimées, et, que doubler 'i' suffit à supprimer les autres.
    # Même optimisé, il reste encore pas mal de suppressions pour rien...
}


#--- on envoie ---------------------------------------------------------------------

    #Recherche_sans_optimisation
    #Recherche_optimisee
    Recherche_finale

    premiers=( ${premiers[@]} ) # On met à jour
    printf "%8d" ${premiers[*]}
    echo -e "\n\n\tIl y a ${#premiers[*]} nombres premiers dans $maxi"

exit 0

Dernière modification par bruno (05-08-2017 00:27:02)

WarLocG

#! modo de compet

Re : script recherche nombres premiers

J'avais déjà fait la même chose en python : https://linuxtrack.net/viewtopic.php?id=1671

Merci pour la version bash

---

Avant de poser vos questions, jeter un oeil ici
Mon CodeVault et Wiki : ici
Les messages privés envers le staff sont uniquement pour les cas d'urgence ou affaires privées (personnelles). Les demandes se feront exclusivement sur le forum. Merci de respecter cette clause sous peine de sanctions.

penthium2

Modérateur

Re : script recherche nombres premiers

je suis tomber sur un truc intéressant pour optimisé les déclaratino de variable intiger et leur incrémentation :
https://askubuntu.com/a/706683

cela optimiserais encore plus ton script je pense.

Merci en tout cas.

---

vi est mon ami pour la vie

Ph'nglui nglw-nafh Cthulhu R'lyeh wgah-nagl fhtagn

bruno

Membre

Re : script recherche nombres premiers

Salut,
merci pour vos liens. Je regarde ça.