Dernière réponse
Sujet : Koment verifier rapidement kun nombre est premier???
yush	Tu calcule le pgcd.   reste(double op1,double op2)// tu te sert de ca apres  {  double result_reste;  double x;  double y;  double resulte;  x = op1/op2;  modf(x, &y);  result_reste=op1-(op2*y);  return result_reste;  }     double pgcd ( double p, double q)  {  //double p_inter,q_inter;  int pgcd_result;  double resultat,r;    if ( reste ( p,q) == 0)   {    resultat=q;   }  else     {    while (pgcd_result != 1)    {     r = reste (p,q);     if ( r==0)     {      pgcd_result = 1;     }    resultat =r;    p=q;    q=r;    pgcd_result =0;         }    }   return resultat; }   Si ca marche pas mail moi car j'ai fait du copier coller depuis un point h.Mais j'ai un prog qui le fait avec cette fonction donc ca devrait etre bon.

Votre réponse
Nom d'utilisateur	Pour poster, vous devez être inscrit sur ce forum .... si ce n'est pas le cas, cliquez ici !
Mot de passe	Vous avez perdu votre mot de passe ? Cliquez ici !
Le ton de votre message
Votre réponse Smilies     Liste des smilies perso Wiki smilies Chercher un smiley
Options	Activer votre signature Désactiver les smilies Activer la notification par email du sujet

Aperçu

Vous avez perdu votre mot de passe ?

Vue Rapide de la discussion

yush

Tu calcule le pgcd.   reste(double op1,double op2)// tu te sert de ca apres  {  double result_reste;  double x;  double y;  double resulte;  x = op1/op2;  modf(x, &y);  result_reste=op1-(op2*y);  return result_reste;  }     double pgcd ( double p, double q)  {  //double p_inter,q_inter;  int pgcd_result;  double resultat,r;    if ( reste ( p,q) == 0)   {    resultat=q;   }  else     {    while (pgcd_result != 1)    {     r = reste (p,q);     if ( r==0)     {      pgcd_result = 1;     }    resultat =r;    p=q;    q=r;    pgcd_result =0;         }    }   return resultat; }   Si ca marche pas mail moi car j'ai fait du copier coller depuis un point h.Mais j'ai un prog qui le fait avec cette fonction donc ca devrait etre bon.

Fouge

Le calcul de max (plutot que i*i a chaque fois) est une bonne idée. Bien entendu, je n'avais pas oublié de vérifier parité de n avant de faire i=i+2. Maintenant, cette fonction m'a l'air plutot bien optimisée! JPA>Encore merci!!!

JPA

A chaque itération tu calcules i*i : perte de temps Fais plutôt : Max = partie entière (racine carrée ( n ) )  / Désolé je connais pas franchement la syntaxe en C (les vieux programment en Fortran ou Pascal) while(i<=Max && prem!=0) ...   Tu remplaces i++ par i+2 APRES avoir testé la non parité de n donc int verif_prem(int n)   {       int i=3,prem=0,Max;     calcul de Max     prem=n%2       while(i<=Max && prem!=0) {prem=n%i; i+2;}       return prem;   }     et là ça doit rouler

verdoux

Riche idée le test "i*i <= n" :D

Fouge

T'as pas bien vu: je me limite à la racine carré avec le test : "i*i<=n" Et pour éviter les nombre pairs, faut ke je remplace "i++" par "i=i+2". Merci pour tout!

JPA	Pas vraiment optimisé ton soft ... Si j'ai bien lu, tu fais 4 fois trop de tests Limite toi à racine carrée de n   -> 2 fois moins Tu testes avec 2,3,4,5,6,7... Il faut que tu enlèves les pairs...  -> 2 fois moins

Fouge

Voici ce que ca donne en C pour les nombres<2147483648 : int verif_prem(int n) {     int i=2,prem=0;     while(i*i<=n && prem!=0) {prem=n%i; i++;}     return prem; } si 0 est renvoyé alors le nombre n'est pas premier sinon le nombre est premier Ya donc pas mieux? (peut-etre la vérification de la parité) Une autre méthode?

JPA

-> toucouch : C'est là que ça se corse : Le pb de fouge était "rapidement" Pour des nombres de 100 chiffres le calcul brut va donner 5 000 000 000 d'itérations avec obligation de réécrire les fonctions pour les grands nombres. Et ça je sais pas faire "rapidement"   On peut bien sur se créer une table ds nombres premiers pour éviter des calculs inutiles, mais comme cette table ne tient pas en mémoire, le chargement de cette table par segments va prendre un temps fou sur le disque.   Les méthodes sur la recherche des grands nombre premiers (actuellement 2^12 000 000 (voir le site www.mersenne.org/prime.htm) recherchent des nombres de Mersenne sous la forme 2^X -1, qui comme tu l'auras remarqué ont la caractéristique de s'écrire en binaire avec uniquement des 1. La vérification de la primalité d'un tel nombre prend plus d'un mois sur un Pentium III 600 MHz. A+

Toucouch

JPA a écrit a écrit : Pour un nombre codé sur 32 bits tu auras au max 32 768 itérations. Le petit progr proposé par Bendes optimisé avec mes observations est suffisant.   J'avais peur que tu veuilles faire des tests sur des nombres de 100 chiffres. Et pour des nombres de 100 chiffres, tu proposes quoi?

JPA	Pour un nombre codé sur 32 bits tu auras au max 32 768 itérations. Le petit progr proposé par Bendes optimisé avec mes observations est suffisant.   J'avais peur que tu veuilles faire des tests sur des nombres de 100 chiffres.

JPA	-> Bendes : limite ta boucle for à partie entière(racine carrée(Nombre)) Tu gagneras du temps Ensuite pour diviser le temps par deux, il faut : 1) tester si le nombre est pair 2) si non : le pas de la boucle est de 2 : teste 3, 5, 7, ...     Cet algo ne marche que pour des petits nombres

Fouge

nombre codé sur 32bits

Bendes

V'là un p'tit code source en VB :   Public Function ESTPREMIER(Nombre as Long) as Boolean Dim i as Integer   ESTPREMIER = True For i = 2 To Nombre - 1     If Nombre Mod i = 0 Then        ESTPREMIER = False        Exit For     End If   DoEvents Next i End Function

JPA	Quelle est la taille de ton nombre ? Les méthodes dépendront de celà...

Fouge

Tout est dit. Quelles sont les != méthodes kon peut utiliser?