Algo nombres premiers

Fermé
jeje_42 - 17 févr. 2009 à 15:59
TiboleParano Messages postés 498 Date d'inscription mardi 18 mars 2008 Statut Membre Dernière intervention 7 avril 2015 - 14 oct. 2009 à 13:34
Bonjour,

Je voudrais créer un algo très simple qui permet de savoir si un nombre est premier ou pas, en calculant le reste de ses divisions successives par tous les nombres qui le précèdent.

Mon script:


#!/bin/bash

ARGS=1

i=2

while [ $(($1%i)) -ne 0 ]
do
i='expr i+1'
done

if [ i -ne $1 ]; then
echo " $1 n'est pas premier ! voici deux diviseurs :"
echo i
echo $(($1/i))
else
echo " $1 est premier !"
fi


Malheureusement, j'ai deux erreurs lorsque je lance par exemple

./script.sh 51

Voici mon output :

./script.sh: line 7: expr i+1: expression recursion level exceeded (error token is "i+1")
./script.sh: line 9: [: i: integer expression expected
51 est premier !

Merci d'avance à tous ceux qui essaieront de m'aider !

Jerome

2 réponses

TiboleParano Messages postés 498 Date d'inscription mardi 18 mars 2008 Statut Membre Dernière intervention 7 avril 2015 61
14 oct. 2009 à 13:34
oui, comme dit LennyPourVoir, pour un algorithme de nombres premiers tu divise le nombre par les entiers jusqu'à sa racine carrée: s'il n'y a pas de solution [=0] avant, il n'y en aura pas d'autres après, et le nombre est premier
ensuite, pour optimiser l'algo, vu qu'au bout d'un certain nombre de nombres (haha) il doit bien ramer, on peut srappeller le théoreme de mon prof de terminale, celui qui explique pourquoi il existe une infinité de nombre premier:
si P[0] est le premier nombre premier (2); P[1] le 2e (3) ... et P[n] le dernier trouvé dans ta liste, alors P[1]*P[2]*...*P[n] n'est pas premier, vu qu'il peut être divisé par les nombres premiers précédents, mais (P[1]*P[2]*...*P[n]) +1 l'est :)
2
LennyPourVoir Messages postés 10 Date d'inscription samedi 14 février 2009 Statut Membre Dernière intervention 18 février 2009 1
17 févr. 2009 à 18:10
#!/bin/bash

i=2

while [ $(($1%i)) -ne 0 ]
do
i=$((i+1))
echo $i
done

if [ $i -ne $1 ]; then
echo " $1 n'est pas premier ! voici deux diviseurs :"
echo $i
echo $(($1/i))
else
echo " $1 est premier !"
fi


Voilà qui devrait mieux marcher, par ailleurs ton algo n'est pas du tout optimisé.
Si le nombre n'est pas divisible par 2 on peut ajouter 2 à i ...
De plus dès que le quotient dépasse le diviseur on peut s'arrêter ....
Pour 51 inutile l'aller jusqu'à 51, jusqu'à 7 suffit ! (7*7=49, 8*8=64)
1