Rechercher
 
 

Résultats par :
 


Rechercher Recherche avancée

Connexion

Récupérer mon mot de passe

Chatbox externe


Derniers sujets
» [JEU] Mon voisin du dessous
Aujourd'hui à 11:52 par Clément.7

» Lancement du TI-Concours 2017 !
Sam 20 Mai 2017 - 0:27 par Paulo1026

» Chaînes Youtube des membres
Ven 19 Mai 2017 - 22:41 par Wistaro

» cacul du taux d'intêret
Ven 24 Mar 2017 - 21:50 par m@thieu41

» [Projet] Un mario by tout82
Dim 29 Jan 2017 - 14:09 par Wistaro

» Cherche documentation assembleur TI82stat
Mer 25 Jan 2017 - 12:29 par Ti64CLi++

» Probleme Ti-82 Stats fr
Jeu 12 Jan 2017 - 13:56 par Ti64CLi++

» ROM 82 stats.fr
Jeu 15 Déc 2016 - 10:24 par Ti64CLi++

» flappy bird
Jeu 15 Déc 2016 - 10:23 par Ti64CLi++

Partenaires
TI-Planet Espace-TI : Forum

Faire un don à Tout-82...
Où va cet argent ?
Membres donateurs:- Persalteas (10€)
- Wistaro (5€)
- jo2geek (22€)

Les posteurs les plus actifs du mois
Wistaro
 
Clément.7
 


Recherche de nombre premier

Poster un nouveau sujet   Répondre au sujet

Voir le sujet précédent Voir le sujet suivant Aller en bas

Recherche de nombre premier

Message par jo2geek le Ven 28 Fév 2014 - 22:09

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

jo2geek
Connaisseur
Connaisseur

Messages : 116
Points Concours : 81
Productivité : 9
Date d'inscription : 27/01/2014
Calculatrice(s) :
  • TI-82 Stats.fr

. : TI-82 Stats.fr

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: Recherche de nombre premier

Message par grmycaire le Ven 28 Fév 2014 - 22:51

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

grmycaire
Intéressé
Intéressé

Messages : 79
Points Concours : 14
Productivité : 7
Date d'inscription : 13/12/2013
Localisation : Embrun
Calculatrice(s) :
  • TI-82 Stats.fr

. : TI-82 Stats.fr

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: Recherche de nombre premier

Message par jo2geek le Sam 1 Mar 2014 - 9:21

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

jo2geek
Connaisseur
Connaisseur

Messages : 116
Points Concours : 81
Productivité : 9
Date d'inscription : 27/01/2014
Calculatrice(s) :
  • TI-82 Stats.fr

. : TI-82 Stats.fr

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: Recherche de nombre premier

Message par Wistaro le Sam 1 Mar 2014 - 12:19

Je ne vois pas d'optimisations, bravo  clapclap 

__________________________________________________________________________
Clique ici pour retrouver tout mes programmes en TIbasic

Tu es curieux, Invité? Alors clique ici:


Coucou Invité !Ta dernière visite sur ce forum date de . Tu as posté un total de 78 message(s) sur Tout 82 et enfin, tu as 0 ans.
Si nous sommes le 0, je te souhaite un joyeux anniversaire ;-)

avatar
Wistaro
Passioné
Passioné

Messages : 906
Points Concours : 86
Productivité : 28
Date d'inscription : 16/06/2013
Localisation : Tarbes - DUT GEII
Calculatrice(s) :
  • TI-82
  • TI-82 Stats
  • TI-82 Stats.fr

. : TI-82 Stats.fr

Voir le profil de l'utilisateur http://www.youtube.com/user/Wistaro

Revenir en haut Aller en bas

Re: Recherche de nombre premier

Message par m@thieu41 le Sam 1 Mar 2014 - 13:35

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

__________________________________________________________________________
ZSNAKE Mon premier (et unique) jeu en ASM:
Un Snake 2 joueurs (2caltos)
-> Je travaille sur une version plus stable du jeu, je poste dès que possible.
avatar
m@thieu41
----------------------
----------------------

Messages : 934
Points Concours : 65
Productivité : 47
Date d'inscription : 02/06/2013
Localisation : Nice, France
Calculatrice(s) :
  • TI-82 Stats.fr

. : TI-82 Stats.fr

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: Recherche de nombre premier

Message par jo2geek le Sam 1 Mar 2014 - 22:09

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 .

jo2geek
Connaisseur
Connaisseur

Messages : 116
Points Concours : 81
Productivité : 9
Date d'inscription : 27/01/2014
Calculatrice(s) :
  • TI-82 Stats.fr

. : TI-82 Stats.fr

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: Recherche de nombre premier

Message par m@thieu41 le Sam 1 Mar 2014 - 22:18

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.

__________________________________________________________________________
ZSNAKE Mon premier (et unique) jeu en ASM:
Un Snake 2 joueurs (2caltos)
-> Je travaille sur une version plus stable du jeu, je poste dès que possible.
avatar
m@thieu41
----------------------
----------------------

Messages : 934
Points Concours : 65
Productivité : 47
Date d'inscription : 02/06/2013
Localisation : Nice, France
Calculatrice(s) :
  • TI-82 Stats.fr

. : TI-82 Stats.fr

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: Recherche de nombre premier

Message par jo2geek le Dim 2 Mar 2014 - 9:12

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

jo2geek
Connaisseur
Connaisseur

Messages : 116
Points Concours : 81
Productivité : 9
Date d'inscription : 27/01/2014
Calculatrice(s) :
  • TI-82 Stats.fr

. : TI-82 Stats.fr

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: Recherche de nombre premier

Message par m@thieu41 le Dim 2 Mar 2014 - 11:51

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.

__________________________________________________________________________
ZSNAKE Mon premier (et unique) jeu en ASM:
Un Snake 2 joueurs (2caltos)
-> Je travaille sur une version plus stable du jeu, je poste dès que possible.
avatar
m@thieu41
----------------------
----------------------

Messages : 934
Points Concours : 65
Productivité : 47
Date d'inscription : 02/06/2013
Localisation : Nice, France
Calculatrice(s) :
  • TI-82 Stats.fr

. : TI-82 Stats.fr

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: Recherche de nombre premier

Message par jo2geek le Dim 2 Mar 2014 - 14:14

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 Smile)
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 .)

jo2geek
Connaisseur
Connaisseur

Messages : 116
Points Concours : 81
Productivité : 9
Date d'inscription : 27/01/2014
Calculatrice(s) :
  • TI-82 Stats.fr

. : TI-82 Stats.fr

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: Recherche de nombre premier

Message par m@thieu41 le Dim 2 Mar 2014 - 14:46

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 Wink
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 Razz 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 Razz) //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.

__________________________________________________________________________
ZSNAKE Mon premier (et unique) jeu en ASM:
Un Snake 2 joueurs (2caltos)
-> Je travaille sur une version plus stable du jeu, je poste dès que possible.
avatar
m@thieu41
----------------------
----------------------

Messages : 934
Points Concours : 65
Productivité : 47
Date d'inscription : 02/06/2013
Localisation : Nice, France
Calculatrice(s) :
  • TI-82 Stats.fr

. : TI-82 Stats.fr

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: Recherche de nombre premier

Message par Linkakro le Sam 8 Mar 2014 - 1:34

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

__________________________________________________________________________
Vétéran du TI-Basic Zilog80. Ti82statfr sur Tout82 depuis 2009 et ti84pocketfr depuis noël 2012. Ti83plusfrUSB (été 2014, concours tiplanet suite du geek). Bidouille un peu d'assembleur Z80.
Incappable de gérer le temps et manque de tact, plutôt serviable.
Je prend les commandes de programme. Je suis motivé par les maths et la physique tant que ce n'est pas une simple copie d'antisèche.
Vous pouvez trouver une grande partie de mes données hébergées dans mon mediafire. Le ZIP et la liste sont périmées depuis longtemps.
coucou Invité What a Face
avatar
Linkakro
----------------------
----------------------

Messages : 533
Points Concours : 55
Productivité : 31
Date d'inscription : 30/07/2013
Localisation : origine région centre, puis perpignan
Calculatrice(s) :
  • TI-82 Stats.fr

. : TI-82 Stats.fr

Voir le profil de l'utilisateur

Revenir en haut Aller en bas

Re: Recherche de nombre premier

Message par Contenu sponsorisé


Contenu sponsorisé


Revenir en haut Aller en bas

Voir le sujet précédent Voir le sujet suivant Revenir en haut

- Sujets similaires

 
Permission de ce forum:
Vous pouvez répondre aux sujets dans ce forum