Recherche de nombre premier

Bonjour
un programme qui dit si un nombre est premier (ou pas ...) cette fonction existe sur TI89 IsPrime( et le résultat est instantané... (true ou false)
Mais ici ce n'est pas le cas car c'est un programme spaghetti et pas du tout rapide surtout si on demande un grand nombre (exemple 997)

mais il semble fonctionner...

Code:

:ClrHome
:Prompt N
:iPart(N→N
:If N<2:Goto N
:If N=2:Goto Y
:If (N-2iPart(N/2)=0:Goto N
:For(I,3,N-1,2
: If (N-IiPart(N/I)=0:Goto N
:End
:Lbl Y
:Disp N,"OUI
:Stop
:Lbl N
:Disp N,"NON

Code:


:If N<2: Goto N
:If (N-2iPart(N/2)=0:Goto N


peut se remplacer par:

Code:


:If N<2 ou (N-2iPart(N/2): Goto N


Bonjour
d'accord sur le "OU" mais pas sur le test si =0
dans http://www.tout82.org/t50-candide-ou-l-optimisation

Samos a écrit:

Code:

If A != 0
aboutit au même résultat que
If A

et

Code:

If A = 0
peut s'optimiser en
If not(A

donc j'écris plutôt

Code:

:ClrHome
:Prompt N
:iPart(N→N
:If N=2:Goto Y
:If N<2 or not(N-2iPart(N/2:Goto N
:For(I,3,N-1,2
:If not(N-IiPart(N/I:Goto N
:End
:Lbl Y
:Disp N,"OUI
:Stop
:Lbl N
:Disp N,"NON

Mais l'optimisation de l'algo doit être possible..
à bientôt

Je ne vois pas d'optimisations, bravo   

Bonjour,

Quelques remarques: tu testes tous les diviseurs de 1 à N... il est plus judicieux de tester de 1 à la racine carrée de N.
Ensuite, utiliser la fonction partDéc (fPart) est plus judicieux à mon avis:

Code:

:ClrHome
:Prompt N
:iPart(N→N
:If N=2
:Goto Y
:If N<2 or not(fPart(.5N
:Goto N
:For(I,3,sqrt(N),2 //sqrt = racine carrée
:If not(fPart(N/I
:Goto N
:End
:Lbl Y
:Disp N,"OUI
:Stop
:Lbl N
:Disp N,"NON

Ensuite, on peut aussi utiliser la fonction seq:

Code:

:ClrHome
:Prompt N
:iPart(N→N
:If N=2
:Goto Y
:If N<2 or not(fPart(.5N
:Goto N
:If fPart(N/seq(A,A,3,sqrt(N),2
:Goto Y
:Lbl N
:Disp N,"NON
:Stop
:Lbl Y
:Disp N,"OUI

Bonsoir
merci des réponses.

Oui j'avais également pensé à utiliser fPart ce qui est de loin plus judicieux mais comme j'avais un code qui marchait je ne l'avais pas encore modifié.

Je ne maitrise pas vraiment seg mais ça à l'air intéressant comme méthode.

je réfléchis aussi à une méthode quasi instantané pour les nombres <1000 .

Quasi instantanée? Comment ferais tu?

seq permet d'obtenir une liste comme suit:
seq(expression,variable,début,fin[pas]
Chaque terme de la liste sera calculé selon l'expression pour la variable allant de début à fin, avec un pas à 1 par défaut.

Bonjour

quasi instantanée (je vais charger une 1er fois les nombres premiers dans un liste...) il doit y en avoir 168 donc après il n'y aura plus de calcul, juste un parcours de la liste

Ta 2eme méthode me dit ERR: INCREMENT

J'avais fait une petite erreur (le test d'une liste...), et l'ERR:INCREMENT vient du fait que pour N<9, la liste renvoyée devrait comporter... 0 termes, ce qui est impossible.

Voici une correction (j'édite mon code plus haut aussi):

Code:

:ClrHome
:Prompt N
:iPart(N→N
:If N=2 or N=3
:Goto Y
:If N<2 or not(fPart(.5N
:Goto N
:If prod(fPart(N/seq(A,A,3,max(3,sqrt(N)),2
:Goto Y
:Lbl N
:Disp N,"NON
:Stop
:Lbl Y
:Disp N,"OUI

J'ai testé, ça devrait marcher.

Super et c'est rapide ! Bravo !  (donc je ne vais rien optimiser puisque 997 me donne la réponde en mois de 2 secondes)

mais quelles sont les limites pour un "résultat juste à 100% " avec cette méthode ? Le nombre de décimales que peut gérer la calculatrice ?

j'ai essayé ( pour (le fun )
132 049 me dit premier (ce qui est vrai)
216 091 me dit non premier (alors que c'est premier)

j'essaierai quand j'aurai accès à la TI89 voir ce qu'elle dit (mais c'est peut-être du 16 ou 32 bit  sur cette machine .)

En effet, ça ne marche pas ici.
Pour une plus grande précision des résultats, essaye ceci (remplace prod par min):

Code:

:ClrHome
:Prompt N
:iPart(N→N
:If N=2 or N=3
:Goto Y
:If N<2 or not(fPart(.5N
:Goto N
:If min(fPart(N/seq(A,A,3,max(3,sqrt(N)),2
:Goto Y
:Lbl N
:Disp N,"NON
:Stop
:Lbl Y
:Disp N,"OUI

Avec ça, tu devrait avoir une erreur mémoire (avec une mémoire pleine vers 4003999 normalement) avant de dépasser la précision.

Après 4003999, il faut utiliser la méthode avec la boucle For (qui normalement donnera toujours des résultats corrects, mais sera également bien plus lente...).

Ex: 4003999 justement est premier, et la calto (avec la méthode seq) trouve bien ce résultat (en seulement 16 secondes!).
4004001 donne un dépassement mémoire.
4003997 n'est pas premier.
4003981 l'est.
Les résultats sont donc cohérents.


Je travaille sur un moyen de faire pour tout nombre jusqu'au maximum que la calto peut traiter, avec seq.


EDIT: J'ai réussi
Donc maintenant tu peux tester jusqu'à 999.999.999.999 (à partir de 14 chiffres tu as une troncature... (d'ailleurs j'ai été surpris je sais plus pourquoi mais j'étais sur que c'était 14 chiffres qu'elle pouvait retenir... mais apparemment non puisque (1E13 + 2 - 1E13) donne 0)).

Voici le code:

Code:

ClrHome
Prompt N
iPart(N→N
If N=2 or N=3
Goto Y
If N<2 or not(fPart(.5N
Goto N
For(D,0,(sqrt(N)-3)/1998
1998D+3
If not(min(fPart(N/seq(A,A,Ans,min(Ans+1996,max(3,sqrt(N))),2
Goto N
End
Lbl Y
Disp N,"OUI
Stop
Lbl N
Disp N,"NON

Il (devrait) marche pour 999.999.999.989 (le plus grand nombre premier inférieur à 1E13 (heu en fait non c'est pas le plus grands autant pour moi Mais le plus grands mettrait 7h05 à vérifier donc bon...), et donc le plus grand que la calto puisse traiter sans se compliquer trop la vie), et trouve que c'est un nombre premier en ~2h15 (j'attends le résultat, ça fait 15 min que je l'ai lancé, mais normalement ça devrait être ça... Je confirme dans 2h ) //Edit: En effet ça donne bien le bon résultat, au bout de 2h15 environ.
Plus accessible: 100000007 est un nombre premier (trouvé en ~1min20s)
100000009 n'est pas un nombre premier (16s)
Généralement, trouver qu'un nombre est premier prends plus de temps que s'il n'est pas premier (moins de tours de boucles à faire puisqu'on s'arrête dès qu'on trouve qu'il n'est pas premier).



Nb: Si tu n'as pas assez de mémoire pour ce prgm (qui utilise des listes de 999 termes soit 9Ko), tu peux:
Changer 1998 par un autre nombre pair (qui vaut 2 fois la taille de la liste).
Changer 1996 par le nombre que tu as choisi moins 2.
Par exemple, si tu ne peux utiliser que ~2Ko:

Code:

For(D,0,(sqrt(N)-3)/400
400D+3
If not(min(fPart(N/seq(A,A,Ans,min(Ans+398,max(3,sqrt(N))),2

On trouve toujours le même résultat mais ce sera un peu plus long par contre.

J'ai l'habitude des cribles en ce qui concerne les nombres premiers, mais je n'ai jamais tenté d'utiliser des listes ainsi. Bien joué m@thieu41.

*avantage For :
incrément et condition de racine léger et rapide
*inconvénient For :
pas de condition d'arrêt anticipé
ou bien usage d'un Goto alors mauvais en algorithmie
problème avec les impairs inférieurs à 11 (la racine inférieure à 3 donc la boucle évitée)
*avantage Repeat : les deux conditions, pas de Goto
*inconvénient Repeat : incrément et condition de racine très lourds

Hormis le Repeat, ceci est simple

Code:

Prompt N
If N=2
Goto 1
If not(fPart(N.5
Goto 0
1->W
sqrt(N->R
Repeat X>R or Ans
X+2->X
not(fPart(N/X
End
If Ans
Goto 0
Lbl 1
Disp "PREMIER
Stop
Lbl 0
Disp "PAS PREMIER

Avec une liste, et mon approche Repeat.
Je préfère avoir comme compteur les bornes explicites W et un pas 1998 plutôt que de travailler tantôt avec D=(W-3)/1998 et W=1998D+3 qui n'ajoutent que des calculs supplémentaires. Si tu veux vraiment t'infliger des calculs, tu pouvais aussi définir les impairs avec 1+2K=W...
Un max(4,sqrt(N))->R pour supporter les impairs dont la racine est inférieure à 3. (3,5,7,9).

Code:

Prompt N
If N=2 or N=3
Goto 1
If not(fPart(N.5
Goto 0
max(4,sqrt(N->R
3->W
Repeat W>R or Ans
W+1998->W
max(not(fPart(seq(N/X,X,W-1998,min(W-1,R),2
End
If Ans
Goto 0
Lbl 1
Disp "PREMIER
Stop
Lbl 0
Disp "NON PREMIER