Décomposition en facteurs premiers avec gmp

Télécharger le projet
Commenter

Description

Voici un programme développé en Visual C++ 6.0 qui calcule la décomposition en facteurs premiers d'un nombre entier positif éventuellement de grande taille. On peut très largement dépasser la limite des int et même des __int64. La bibliothèque gmp : http://cs.nyu.edu/exact/core/gmp/ est donc utilisée pour cette raison. La documentation gmp-man-4.1.2.pdf est encore disponible. La méthode de calcul est simplement la méthode naïve. Le temps de calcul est très variable, il peut être excessivement long quand on rencontre un nombre premier de très grande taille. C'est en fait, un exemple simple pour montrer l'utilisation de gmp. Pour un test de primalité, ce n'est pas toujours un très bon exemple. On s'intéresse ici uniquement à la décomposition en facteurs premiers.

Source / Exemple : 


#include <stdio.h>
#include <stdlib.h>
#include <gmp.h>
int main (int argc, char *argv[]) {  // décomposition d'un entier n quelconque 
    mpz_t n,i,ii,q;                  // en produit de nombres premiers
    unsigned int s,t[]={4,2,4,2,4,6,2,6};
    mpz_init(n);	
    mpz_init(i);	
    mpz_init(ii);	
    mpz_init(q);	
//   lecture du nombre n à décomposer
    if(argc==2) gmp_sscanf(argv[1],"%Zd",n);
    else {       
        input: printf("\nEntrez un nombre entier plus grand que 1 : ");
        gmp_scanf("%Zd",n);
        if(mpz_cmp_si(n,2)<0) goto input;  // if(n<2) goto input
    } 
    s=2;
//   est-ce que s divise n une ou plusieurs fois ?
    prems : if(mpz_cmp_ui(n,s)==0) goto fin;   // si n = s
    if(mpz_divisible_ui_p(n,s)) {              // si s divise n
        mpz_div_ui(q,n,s);                     // q = n / s
        gmp_printf("\n\n %Zd = %Zd * %d",n,q,s); 
        mpz_set(n,q);                          // n = n / s
        goto prems;
    }
    if(s==2) {s=3; goto prems;}
    if(s==3) {s=5; goto prems;}
    s=0;
    mpz_set_si(i,7);                   // i = 7
    mpz_set_si(ii,49);                 // ii = 49
//    à partir de i, calcul du plus petit diviseur i de n ( i sera premier )
    boucle: for(;;) {                  // pour chaque valeur de i 
        if(mpz_cmp(ii,n)>0) goto fin;  // if(i*i>n) : donc n est premier 
        if(mpz_divisible_p(n,i)!=0) {  // si i divise n 
            mpz_div(q,n,i);            // q = n / i
            gmp_printf("\n\n %Zd = %Zd * %Zd",n,q,i);
            mpz_set(n,q);              // n = n / i
            goto boucle;
        }
        else {                       // si i ne divise pas n on devrait prendre pour i le nombre
            mpz_add_ui(i,i,t[s++]);  // premier suivant, mais il n'est pas connu. Donc, on prend
            if(s==8) s=0;            // l'entier suivant en évitant les multiples de 2, 3 et 5
            mpz_mul(ii,i,i);         // ii = i * i
        }
    }
    fin: gmp_printf("\n\n %Zd est premier\n\n\n",n); 
    mpz_clear(n);	
    mpz_clear(i);	
    mpz_clear(ii);	
    mpz_clear(q);	
    system("pause");
    return 0;
}

Conclusion :


On peut l'utiliser en cliquant sur diviseurs.exe ou avec un raccourci ou encore avec un fichier *.bat. Toutes remarques ou améliorations sont les bienvenues. Merci, pgl10
Télécharger le projet

Codes Sources

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