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

Commenter

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

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 (darkor)