Calcul du PGCD et du PPCM

Le plus grand commun diviseur (PGCD) de deux entiers s'obtient efficacement via l'algorithme d'Euclide. Une version itérative élimine les risques de débordement de pile tout en conservant une complexité logarithmique :

int calculer_PGCD(int val_a, int val_b) {
    while (val_b != 0) {
        int residu = val_b;
        val_b = val_a % val_b;
        val_a = residu;
    }
    return val_a;
}

Le plus petit commun multiple (PPCM) se déduit mathématiquement de cette relation : PPCM(a, b) = (a / PGCD(a, b)) \* b. Effectuer la division avant la multiplication évite les dépassements d'entier lorsque les operands sont proches de INT\_MAX.

Identification des Nombres Premiers

Un entier supérieur à 1 est qualifié de premier s'il admet uniquement 1 et lui-même comme diviseurs. Tester tous les entiers jusqu'à n est inefficient ; il suffit de vérifier les diviseurs potentiels jusqu'à $\sqrt{n}$. En isolant le cas pair et en incrémentant de 2, le nombre d'itérations est réduit de moitié :

bool tester_Premier(int candidat) {
    if (candidat <= 1) return false;
    if (candidat == 2) return true;
    if (candidat % 2 == 0) return false;

    int borne_superieure = static_cast<int>(std::sqrt(static_cast<double>(candidat)));
    for (int div = 3; div <= borne_superieure; div += 2) {
        if (candidat % div == 0) return false;
    }
    return true;
}</double></int>

Prétraitement par Crible

Lorsque plusieurs requêtes de vérification de primalité concernent une même plage bornée, précalcluer les nombres premiers gagne considérablement en temps d'exécution. Le crible marque systématiquement les composés en parcourant les multiples à partir de chaque base identifiée comme première :

constexpr int PLAFFOND = 100000;
bool est_compose[PLAFFOND + 1] = {};
std::vector<int> reseaux_premiers;

void generer_Crible() {
    std::fill(std::begin(est_compose), std::end(est_compose), false);
    est_compose[0] = est_compose[1] = true;

    for (int i = 2; i <= PLAFFOND; ++i) {
        if (!est_compose[i]) {
            reseaux_premiers.push_back(i);
            for (long long multi = 1LL * i * i; multi <= PLAFFOND; multi += i) {
                est_compose[multi] = true;
            }
        }
    }
}

Cette structure attient des performances quasi-linéaires pour des seuils inférieurs à $10^6$. Pour des contraintes mémoire très resserrées, une variante linéaire peut être implémentée en ne marquant chaque composé qu'une seule fois via son plus petit facteur premier.

Factorisation en Produits Premiers

Décomposer un entier $N$ consiste à extraire ses facteurs fondamentaux ainsi que leurs puissances associées. L'algorithme exploite le crible pour balayer les candidats possibles jusqu'à $\sqrt{N}$, puis traite le résidu éventuel :

#include <cstdio>
#include <cmath>
#include <vector>

struct ElementFacteur {
    int base;
    int exposant;
};

constexpr int SEUIL_CIBLE = 100000;
bool marquage[SEUIL_CIBLE + 1];
std::vector<int> bases_p;
std::vector<ElementFacteur> resultats;

void preparer_Base() {
    marquage[0] = marquage[1] = true;
    for (int i = 2; i <= SEUIL_CIBLE; ++i) {
        if (!marquage[i]) {
            bases_p.push_back(i);
            for (int j = 2 * i; j <= SEUIL_CIBLE; j += i) {
                marquage[j] = true;
            }
        }
    }
}

int main() {
    int nombre_a_decomposer;
    scanf("%d", &nombre_a_decomposer);
    preparer_Base();

    int limite_test = static_cast<int>(std::sqrt(nombre_a_decomposer));
    for (const int& b : bases_p) {
        if (b > limite_test) break;
        if (nombre_a_decomposer % b == 0) {
            ElementFacteur elem;
            elem.base = b;
            elem.exposant = 0;
            while (nombre_a_decomposer % b == 0) {
                elem.exposant++;
                nombre_a_decomposer /= b;
            }
            resultats.push_back(elem);
        }
    }
    if (nombre_a_decomposer > 1) {
        resultats.push_back({nombre_a_decomposer, 1});
    }

    for (const auto& f : resultats) {
        printf("%d %d\n", f.base, f.exposant);
    }
    return 0;
}

La phase principale du parcours reste contrainte par la racine carrée du nombre initial, offrant une complexité théorique en $O(\sqrt{N})$. Si un résidu supérieur à 1 subsiste après l'itération complète, cet élément correspond obligatoirement à un facteur premier unique dont la valeur excède la borne initiale de test.