Factorisation d'un nb composé en 2 premiers (par attack en force brute)

Commenter

Contenu du snippet

Slt,
un ptit prog ki permet de trouver les 2 facteurs premiers d'un nombre composé...
Nb = nombre à factoriser et a et b les 2 facteur premiers (avec a <= (inf ou egal) b)
on test (Nb/i=entier)? avec i decrivant l'ensemble des premiers de 2 à sqrt(Nb) (enfin o nb premier inferier et le plus "proche" de sqrt(Nb))
si le test est verifié alors i=a et Nb/i =b
pour l'instant c limiter au int (ou au long) ...

Source / Exemple : 


#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++;
	}
}

Conclusion :


je me suis inspiré d'un source du site pour la fonction EstPremier (jme souviens plus ki est l'auteur mais il se reconnaitra et je l'en remercie)

il y a un warning à la sortie de la fonction EstDiviseur si kukun c pourkoi??

A voir également

S'inscrire maintenant

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.

Du même auteur (Orkblutt)