0/5 (4 avis)
Snippet vu 3 792 fois - Téléchargée 37 fois
#include <iostream.h> #include <math.h> bool EstPremier ( long N) //d'autre algo st dispo sur le site mé celui ci (enpreinté ossi sur le site) fonctionne // trés bien sur les petits nbs (ca commence à ramer vers 10000000) { long i; if (N<2) return false; if (N==2) return true; if (N % 2 == 0) return false; i = 3; while (i<N) { if (N % i == 0) return false; i += 2; } return true; } bool EstDiviseur (long UnNb, long UnI) //si le rest e de la div euclidienne d'un nb composé par un premier est nul alors le resultat //de la division (normal ;-)) est lui ossi un premier!! { if (UnNb%UnI==0) return true; else return false; } void main () { long Nb; long i=2; bool Trouver=false; cout<<"Nb a factoriser? (ne pas depasser 2 147 483 647 car g po implementer la classe sur les grand nb) "<<endl; cin>> Nb; while (i<=sqrt(Nb) && !Trouver) //Nb=a*b //soit a le facteur premier le plus petit //<=> 2<a<b (c des inf ou egal) //=> a*a<a*b (a²<a*b et a*b==Nb) //<=>a<sqrt(Nb) (sqrt(Nb) c la racine carré de Nb) { if (EstPremier(i)) { if (EstDiviseur(Nb,i)) { Trouver=true; cout<<i; cout<<" et "; cout<< Nb/i; cout<<" sont les facteurs premiers de "; cout<<Nb>>endl; } }; i++; } }
14 févr. 2005 à 23:42
"tout nb premier superieur ou égal à 5 est de la forme 6*n-1 ou 6*n+1 avec n entier naturel"
On ne génére pas que des premiers avec une fonction du type f(x)= { 6x-1 , 6x+1} mais cela n'as aucune importance si l'on veut "attaquer" en force un nb (plus couteux de faire des test de primalité, meme très très basique, que de tester ts les nb générés par f(x)...)
14 févr. 2005 à 23:38
on test tous les nombres impaires supèrieurs à 2...
pour générer tous les premiers dans un intervalle donné, il est beaucoup moins couteux d'utiliser l'axiom "tout nb premier superieur ou égal à 5 est de la forme 6*n-1 ou 6*n+1 avec n entier naturel"...
Pour factoriser un entier la brute force est la mèthode la moins performante. Pour des nombres spéciaux ECM ou SNFS sont parfait (ECM pour des nombres a environ 100 digits et jusquà 180 digits pour SNFS). Pour des nombres dont les 2 facteurs premiers sont du meme ordre de grandeure que N (clef RSA...) GNFS est l'algo le plus rapide à ce jour (factorisation d'une 576bits en decembre 2003). Les variantes des cribles quadratiques
marchent très bien sur des nb inférieurs à ~100digits...
14 févr. 2005 à 22:39
31 déc. 2002 à 10:46
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.