Problème : Trouver la valeur maximale de p telle que x = bp, où b est un entier. Par exemple, 25 = 52 et 64 = 26. L'entrée est x, la sortie est p.

La solutino repose sur la décomposition en facteurs premiers du nombre donné, followed par le calcul du PGCD des exposants.

Fonction de décomposition en facteurs premiers :

int facteurs[100];
int exposants[100];
int indice = 0;

for(int diviseur = 2; nombre != 1; ++diviseur)
{
    if(nombre % diviseur == 0)
    {
        facteurs[indice] = diviseur;
        
        while(nombre % diviseur == 0)
        {
            exposants[indice]++;
            nombre /= diviseur;
        }
        
        indice++;
    }
    if(diviseur > 10000) break;
}
if(nombre > 1)
{
    facteurs[indice] = nombre;
    exposants[indice++] = 1;
}

Deux approaches sont possibles :

Méthode 1 : Division par essaiLa complexité temporelle worst-case atteint approximativeemnt 108 × n. Cette méthode peut échouer avec des données volumineuses. Le point faible apparaît quand le nombre contient un grand facteur premier ou plusieurs facteurs proches de ce dernier.

#include <cstdio>

int pgcd(int a, int b)
{
    return b == 0 ? a : pgcd(b, a % b);
}

int main()
{
    int nombre;
    while (scanf("%d", &nombre), nombre != 0)
    {
        int exposant = 0;
        bool negatif = false;
        int resultat = 0;
        bool initial = false;
        
        if (nombre < 0)
        {
            negatif = true;
            nombre = -nombre;
        }
        
        for (int diviseur = 2; nombre > 1; ++diviseur)
        {
            if (nombre % diviseur == 0)
            {
                exposant = 0;
                while (nombre % diviseur == 0)
                {
                    nombre /= diviseur;
                    ++exposant;
                }
                
                if (!initial)
                {
                    resultat = exposant;
                    initial = true;
                }
                else
                {
                    resultat = pgcd(resultat, exposant);
                }
            }
            
            if (diviseur > 1000000) break;
        }
        
        if (nombre > 1) resultat = 1;
        
        if (negatif)
        {
            while (resultat % 2 == 0) resultat /= 2;
        }
        
        printf("%d\n", resultat);
    }
    
    return 0;
}

Méthode 2 : Crible d'Ératosthène + DécompositionLa complexité temporelle est O(106 + n), beaucoup plus efficace.

#include <cstdio>

const int LIMITE = 1000000;

int listePremiers[LIMITE];
bool marque[LIMITE];
bool estPremier[LIMITE];

int genererPremiers()
{
    int nombrePremiers = 0;
    for (int i = 2; i <= LIMITE; ++i)
    {
        if (!marque[i])
        {
            listePremiers[nombrePremiers++] = i;
            estPremier[i] = true;
        }
        
        for (int j = 0; j < nombrePremiers && i * listePremiers[j] <= LIMITE; ++j)
        {
            marque[i * listePremiers[j]] = true;
            if (i % listePremiers[j] == 0) break;
        }
    }
    return nombrePremiers;
}

int pgcd(int a, int b)
{
    return b == 0 ? a : pgcd(b, a % b);
}

int main()
{
    int total = genererPremiers();
    int nombre;
    
    while (scanf("%d", &nombre), nombre != 0)
    {
        int exposant = 0;
        bool negatif = false;
        int resultat = 0;
        bool initial = false;
        
        if (nombre < 0)
        {
            negatif = true;
            nombre = -nombre;
        }
        
        for (int i = 0; i < total; ++i)
        {
            if (nombre % listePremiers[i] == 0)
            {
                exposant = 0;
                while (nombre % listePremiers[i] == 0)
                {
                    nombre /= listePremiers[i];
                    ++exposant;
                }
                
                if (!initial)
                {
                    resultat = exposant;
                    initial = true;
                }
                else
                {
                    resultat = pgcd(resultat, exposant);
                }
            }
        }
        
        if (nombre > 1) resultat = 1;
        
        if (negatif)
        {
            while (resultat % 2 == 0) resultat /= 2;
        }
        
        printf("%d\n", resultat);
    }
    
    return 0;
}