Algorithme de facteur premier : C, Python Exemple

Qu'est-ce qu'une factorisation première ?

Le facteur premier d'un nombre est un facteur qui est lui-même un facteur premier. nombre premier, divisible seulement par 1 et par lui-même.

Exemple : Les facteurs premiers de 10 sont 2 et 5, puisque 2 × 5 = 10.

Trouver les facteurs premiers à l'aide de l'itération

Parcourez les nombres de 2 à √n et vérifiez la divisibilité. Tant que n est divisible par le candidat actuel, effectuez la division et affichez le résultat.

Exemple : tout nombre premier supérieur à 40 correspond à n²+n+41, donc n = 0, 1, 2 donne 41, 43, 47.

Comment imprimer le facteur premier d'un nombre ?

• Parcourir les nombres de 2 à sqrt(n).
• Vérifiez le module de n pour chaque candidat ; un reste nul signifie que le candidat est un facteur premier.
• Récupérez tous les nombres premiers qui divisent n.
• La routine s'exécute en complexité temporelle O(sqrt(n)).

Algorithme:

Set a counter i to 2
While i <= sqrt(n):
    While n % i == 0:
        n = n / i
        print i
    i = i + 1
if n > 1:
    print n

Algorithme de tamisage

La méthode du crible stocke le plus petit facteur premier de chaque nombre jusqu'à une limite maximale, réduisant ainsi considérablement le coût de la factorisation après le précalcul.

• Enregistrez le plus petit facteur premier de chaque entier jusqu'à la limite maximale.
• Prenez le plus petit nombre premier et ajoutez-le à l'ensemble des facteurs.
• Divisez le nombre par ce nombre premier et répétez l'opération jusqu'à ce qu'il atteigne 1.
• Chaque requête s'exécute en environ O(log n).

Exemple : un nombre premier autre que 2 et 3 correspond à la forme 6n-1 ou 6n+1. Par exemple, 5 = 6(1)-1 et 19 = 6(3)+1.

Algorithme: définir un tableau qui stocke le plus petit facteur premier de chaque nombre, en utilisant l'indice comme valeur initiale pour chaque élément.

Set array[1] to 1
Set i to 2
While i*i <= max_number:
    If array[i] == i:
        Set j to i*i
        While j <= max_number:
            If array[j] == j:
                array[j] = i
            j = j + i
    i = i + 1
while the_number != 1:
    print array[the_number]
    the_number = the_number / array[the_number]

Articles Relatifs

• Structure des données graphiques et Algorithms
• Problème de voyageur de commerce
• Algorithme de méthode de bissection
• Algorithme de tri par seau

Python Facteurs premiers utilisant l'itération

Python Le code trouve les facteurs premiers en utilisant la méthode itérative de division par essais successifs :

import math
def PrimeFactors(n):
    for i in range(2, int(math.sqrt(n)) + 1, 1):
        while n % i == 0:  # find all the occurrences of a prime factor
            print((int)(i))
            n = n // i
    if n != 1:  # if the number was originally a prime
        print((int)(n))
n = (int)(input("Enter the number you want: "))
PrimeFactors(n)

Sortie :

Enter the number you want: 4
2
2

Python Facteurs premiers utilisant la récursion

Le Python Le code ci-dessous utilise la méthode du crible pour trouver les facteurs premiers d'un nombre donné.

import math
High = (int)(1e5 + 7)
array = [0 for i in range(High)]

# generate smallest prime factors
def Sieve():
    for i in range(1, High):
        array[i] = i
    for i in range(2, math.ceil(math.sqrt(High))):
        if array[i] == i:
            for j in range(i * i, High, i):
                if array[j] == j:
                    array[j] = i

def PrimeFactors(n):  # divide until we reach 1
    if n == 1:
        return
    print((int)(array[n]))
    PrimeFactors((int)(n / array[n]))

Sieve()
n = (int)(input("Enter the number you want: "))
PrimeFactors(n)

Sortie :

Enter the number you want: 4
2
2

Programme de facteurs premiers C utilisant l'itération

La même solution itérative écrite en C: entrez un nombre, puis pour chaque candidat de 2 à sqrt(n), vérifiez la divisibilité et affichez chaque occurrence d'un facteur premier.

#include <stdio.h>
int main()
{
    int n;
    printf("Enter the number you want: ");
    scanf("%d", &n);
    for (int i = 2; i * i <= n; i++)
    {
        while (n % i == 0)  // find all the occurrences of a prime factor
        {
            printf("%d\n", i);
            n /= i;
        }
    }
    if (n != 1)  // if the number was originally a prime
    {
        printf("%d", n);
    }
    return 0;
}

Sortie :

Enter the number you want: 2
2

Programme de facteurs premiers C utilisant la récursion

La version C récursive reflète le Python une : construire le tableau des plus petits facteurs premiers, puis effectuer une division récursive par ce facteur jusqu'à ce que n atteigne 1.

#include <stdio.h>
int Max = 100007;
int array[100007];

void Sieve()  // smallest prime factors up to Max
{
    for (int i = 1; i < Max; i++)
        array[i] = i;
    for (int i = 2; i * i <= Max; i++)
    {
        if (array[i] == i)
        {
            for (int j = i * i; j < Max; j += i)
            {
                if (array[j] == j)
                    array[j] = i;
            }
        }
    }
}

void PrimeFactors(int n)
{
    if (n == 1)  // divide until we reach 1
        return;
    printf("%d\n", array[n]);
    PrimeFactors(n / array[n]);
}

int main()
{
    Sieve();
    int n;
    printf("Enter the number you want: ");
    scanf("%d", &n);
    PrimeFactors(n);
    return 0;
}

Sortie :

Enter the number you want: 2
2

Quelques faits intéressants sur les nombres premiers

• Tout nombre pair autre que 2 peut être écrit comme la somme de deux nombres premiers (4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3).
• Il n'existe pas d'autres nombres premiers consécutifs que 2 et 3, car 2 est le seul nombre premier pair.
• Tous les nombres premiers, sauf 2 et 3, correspondent à la forme 6n + 1 ou 6n − 1, où n est un entier positif.
• L'ensemble des facteurs premiers d'un nombre est unique.
• Le nombre 1 n'est ni premier ni composé.
• La décomposition en facteurs premiers facilite la divisibilité, la simplification des fractions et la recherche de dénominateurs communs.
• La décomposition en facteurs premiers est également à la base des codes cryptographiques numériques.

FAQ