Factorisation d'un entier en produit de nombres premiers avec une fonction récursive

Soyez le premier à donner votre avis sur cette source.

Snippet vu 9 461 fois - Téléchargée 20 fois

Contenu du snippet

Ce programme affiche les facteurs premiers composant le nombre entré en paramètre, grâce à un algorithme de récurrence très rapide, et très efficace, même avec les grands nombres.

La fonction qui détermine si un nombre est premier commence par tester sa parité (si paire, pas premier...). Ensuite, il teste le modulo de tous les nombres impaires compris entre 3 et la racine du nombre.

La fonction qui trouve les facteurs teste tous les nombres compris entre 2 et la racine du nombre. Si un nombre est un diviseur de n:
  • Si ce diviseur est premier:
  • Affiche ce diviseur
  • Divise n par ce nombre
  • Recommence la recherche, entre 2 et la racine du n initial pour trouver les autres diviseurs
  • Si ce diviseur n'est PAS premier:
  • Récursivité avec le diviseur non-premier en paramètre afin de décomposer ce nombre
  • Recommence la recherche, entre 2 et la racine du n initial pour trouver les autres diviseurs

Source / Exemple :


#include <stdio.h>
#include <conio.h>
#include <math.h>

void PrintFactor(unsigned int n)
{
    //Affichage d'un facteur à l'écran
    printf("Un facteur est: %d\n", n);
    return;
}

//Cette fonction teste si un nombre
//est premier ou pas.
// true: Est premier
// false: N'est pas premier
bool IsPrime(unsigned int n)
{
    if (n<=2)return(true);

    //Ici, on vérifie directement s'il est
    //paire. Si oui, il n'est surement pas
    //premier...
    if (n%2==0)return(false);

    /* La limite de la plage de test
       est la racine carrée du nombre à tester:
           RACINE( n ) * RACINE( n ) = n
       donc si il y a un diviseur, il sera forcemement
       compris entre 1 et RACINE( n )

  • /
unsigned int sq = pow(n, 0.5); //On test le modulo de tous les //nombres impaires entre 3 et RACINE( n ) for (int i=3;i<sq+1;i+=2) if (n%i==0)return(false); return(true); } void fact(unsigned int n) { //n premier ? //On quitte après avoir affiché le nombre if (IsPrime(n)==true) { PrintFactor( n ); return; }; unsigned int sq = pow(n, 0.5); unsigned int i = 2; //On sait que si il y a un diviseur, //premier ou non, il sera compris entre 2 et RACINE( n ) while (i<sq+1) { if ( n%i==0 ) { if ( IsPrime( i ) ) { /* Si i est un diviseur premier,
  • on l'affiche, puis on continue les recherches
  • sur le quotient de n par i
  • /
PrintFactor( i ); n = (n / i); i = 1; } else { //i est un diviseur non-premier ? //on approffondit la recherche des facteurs //sur ce nombre avec la récurrence sur fact( unsigned int ) fact( i ); i = 1; }; }; //Le nombre n est finalement premier après //avoir été réduit, alors on affiche ce nombre, //qui sera donc le dernier facteur du n initial. if ( IsPrime( n ) ) { PrintFactor( n ); return; }; i++; }; return; } int main(void) { unsigned int nbr = 0; printf("Entrez un nombre: "); scanf("%d", &nbr); fact(nbr); getch(); return(0); }

A voir également

Ajouter un commentaire

Commentaires

opossum_farceur
Messages postés
148
Date d'inscription
lundi 16 août 2004
Statut
Membre
Dernière intervention
14 novembre 2009
-
Hi!
Utiliser la fonction "sqrt" plutôt que "pow" (qui fait appel à l'exponentielle) te permettrait certainement de gratter quelques millisecondes pour les nombres importants. J'ai pas testé ton code mais ton algorithme a l'air intéressant.
cs_christianparis
Messages postés
1
Date d'inscription
mercredi 6 août 2008
Statut
Membre
Dernière intervention
1 mars 2010
-
Salut,
Il semble que tu pourrais accélérer ton algorithme...
En regardant la fonction Isprime : à la ligne 36, quand IsPrime() retourne false, la valeur de i est le plus petit des facteurs premiers de n. Or tu ne te sers pas de ce résultat, si bien qu'à la ligne 60, lorsque IsPrime() est false(), tu appelles à nouveau fact() pour retrouver ce résulat déjà calculé...
Dans la boucle while de la ligne 56 à la ligne 89, tu incrémentes i de 1 (ligne 88): la moitié des valeurs de i dans cette boucle seront donc des nombres pairs(qui n'auront aucune chance d'être premiers), ce que tu pourrais éviter en incrémentant de 2 en 2(en commençant par la valeur 3, après avoir fait un cas particulier en tout début de programme pour le diviseur 2)
azizyah
Messages postés
1
Date d'inscription
dimanche 21 février 2010
Statut
Membre
Dernière intervention
1 mars 2010
-
Je n'ai pas encore utilisé ce code. mais il parait que la logique de l'editeur ne se base sur aucune logique de mathematicien. il dit clairement " La fonction qui détermine si un nombre est premier COMMENCE PAR TESTER SA PARITE3 -ET LE PLUS GRAVE -(SI PAIRE PAS PREMIER...)" totalement faut car 2 est paire et il est premier.
posté par: Aziz YAHIAOUI - Architecte - demeurant à Sour El Ghozlane, Algérie- Email azizyah@msn.com
bonne continuation.
tagtog
Messages postés
7
Date d'inscription
mardi 17 février 2009
Statut
Membre
Dernière intervention
20 juillet 2011
-
Merci Pour le code, il est très intéressant pour calcule quelques problèmes mathématique, a bien tôt pour la deuxième version!

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.