[Algo] Calcul de facteurs premiers ?

TITM4v3rick · 17 Déc 2003

Bon voilà, je me demandais si qqn dans "la salle" savait ou connaissait un algorythme de calcul de facteurs premiers sur base d'un nombre ?

Pour rappel :

1 = 1
2 = 2
3 = 3
4 = 2^2
5 = 5
6 = 2 x 3
7 = 7
8 = 2^3
9 = 3^2
10 = 2 x 5

etc...

Bon j'en ai mis un au point en C++ mais il a une limite...
Et j'aime pas les limites, enfin voyez :

Le but de cet algo est de mettre dans un vecteur (ou tableau) tous les facteurs premiers d'un nombre passé en paramètre à la fonction...

Code:

vector &lt; unsigned long > outils::getFacteursPremiers2(long val)
{
    vector &lt; unsigned long > v;
    unsigned long valeur=0;
    if (val &lt; 0)
        valeur = -val;
    else
        valeur = val;
    unsigned long d = 2;

    while (d != 2E32) {
        while (!(valeur % d)) {
            v.push_back(d);
            valeur = valeur/d;
        }
        d++;
        if (valeur &lt; 2) // pour ne pas boucler longtemps inutilement
            break;
    }

    if (valeur > 1)
        v.push_back(valeur);

    return v;
}

Note : je v essayer de faire une version récursive dont la limite serait la "pile" ...

Machiavel666 · 18 Déc 2003

En fait après avoir bien examiner ton algorithme, je vois pas comment tu pourrais dépasser ta limite. A moins que tu ne décide de définir un nouveau type entier qui serait constitué de deux long (avec redéfinition des opérateurs et tout), tu sera toujours limité par la capacité des variables en C++
(a moins que j'ai mal compris ce que tu demandais...).

Au fait je viens de vérifier dans un book : la plus grande valeur qu'on peut mettre dans un entier long non signé, c'est
4 294 967 295 qui devrait remplacer 9999999999999 dans ton while car c'est une trop grande valeur.

TITM4v3rick · 18 Déc 2003

Cpt Machiavel a dit:
En fait après avoir bien examiner ton algorithme, je vois pas comment tu pourrais dépasser ta limite. A moins que tu ne décide de définir un nouveau type entier qui serait constitué de deux long (avec redéfinition des opérateurs et tout), tu sera toujours limité par la capacité des variables en C++
(a moins que j'ai mal compris ce que tu demandais...).

Au fait je viens de vérifier dans un book : la plus grande valeur qu'on peut mettre dans un entier long non signé, c'est
4 294 967 295 qui devrait remplacer 9999999999999 dans ton while car c'est une trop grande valeur.

LoL, tu sais pas dire 2^32 comme tout le monde ?
Voilà mis à jour...

[Algo] Calcul de facteurs premiers ?

TITM4v3rick

1337

Machiavel666

ex membre

TITM4v3rick

1337

Autres sujets récents