Koment verifier rapidement kun nombre est premier???

Koment verifier rapidement kun nombre est premier??? - Programmation

Marsh Posté le 22-03-2001 à 10:16:20    

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

Reply

Marsh Posté le 22-03-2001 à 10:16:20   

Reply

Marsh Posté le 22-03-2001 à 10:22:18    

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

Reply

Marsh Posté le 22-03-2001 à 10:23:13    

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

Reply

Marsh Posté le 22-03-2001 à 10:33:57    

nombre codé sur 32bits

Reply

Marsh Posté le 22-03-2001 à 10:35:25    

-> 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

Reply

Marsh Posté le 22-03-2001 à 10:38:55    

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.

Reply

Marsh Posté le 22-03-2001 à 10:58:34    

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?

Reply

Marsh Posté le 22-03-2001 à 11:16:43    

-> 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+

Reply

Marsh Posté le 22-03-2001 à 14:40:54    

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?

Reply

Marsh Posté le 22-03-2001 à 16:33:53    

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

Reply

Marsh Posté le 22-03-2001 à 16:33:53   

Reply

Marsh Posté le 22-03-2001 à 17:39:48    

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!

Reply

Marsh Posté le 22-03-2001 à 17:46:54    

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

Reply

Marsh Posté le 22-03-2001 à 17:51:18    

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

Reply

Marsh Posté le 22-03-2001 à 18:13:35    

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!!!

Reply

Marsh Posté le 22-03-2001 à 20:51:55    

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.

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed