Algorithme de facteur premier : C, Python Exemple

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

Le facteur premier d'un donné tout le nombre est le facteur qui est un nombre premier. Les facteurs multipliés vous donnent un autre nombre. Un nombre premier est divisible par lui-même ou 1 .

En d’autres termes, les facteurs premiers sont déterminés en trouvant quels nombres premiers se multiplient pour former le nombre d’origine.

Exemple: Les facteurs premiers de 10 sont 2 et 5. En effet, 2X5 = 10 et les deux 2,5 sont des nombres premiers.

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

Pour trouver les facteurs premiers d’un nombre donné, nous parcourons d’abord tous les nombres de 2 jusqu’à la racine carrée du nombre, puis vérifions si chaque nombre est premier. Tant que le nombre d'origine est divisible par ce nombre premier, nous continuons à ajouter ce nombre premier à chaque itération.

Mise en situation :

Tout nombre premier supérieur à 40 s'écrit dans la formule suivante : n²+n+41. Ainsi, nous pouvons remplacer n par tous les nombres pour trouver le facteur premier correspondant. par exemple, 0²+0+41=41, 1²+1+41=43, 2²+2+41=47,…

Comment imprimer le facteur premier d'un nombre ?

• Dans cette méthode, nous allons parcourir les nombres de 2 jusqu'à la racine carrée du nombre, comme mentionné dans la section précédente.
• Pour cela, il faut vérifier le module du nombre d'origine sur chacun des nombres de 2 jusqu'à la racine carrée de n .
• Ensuite, on trouve la liste des nombres premiers qui sont facteurs de n.
• Cette solution est 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 Sieve repose sur le stockage du plus petit facteur premier des nombres, ce qui réduit considérablement la complexité lors du calcul des facteurs premiers pour n'importe quel nombre. L'algorithme Sieve trouve tous les facteurs premiers de manière assez efficace.

• Le concept principal de cet algorithme est de stocker le plus petit facteur premier de chaque nombre jusqu'au nombre maximum.
• Nous prenons le plus petit nombre premier pour chaque nombre donné et l’ajoutons à l’ensemble des facteurs premiers.
• Enfin, nous divisons par ce nombre premier et répétons ces étapes jusqu'à atteindre 1.
• Tout cela se fait dans une complexité temporelle O(log(n)), améliorant considérablement l'efficacité de la solution.
• Ce qui permet de calculer les facteurs premiers de nombres bien plus grands que ceux que l’on aurait pu traiter avec l’approche précédente.

Mise en situation :

La deuxième façon consiste à vérifier si le nombre peut être écrit sous la forme 6n-1 ou 6n+1, car tout nombre premier autre que 2 et 3 doit être écrit dans l'une des deux formules. par exemple, 5=6(1)-1, 19=6(3)+1,… .

Algorithme:

Définissez un tableau pour stocker le plus petit facteur premier de chaque nombre avec la valeur d'index comme valeur initiale pour chaque élément du tableau.

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]

Python Facteurs premiers utilisant l'itération

Ici, nous allons montrer un code dans Python langage pour trouver les facteurs premiers d'un nombre donné dans une méthode itérative :

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
4

Python Facteurs premiers utilisant la récursion

Cette section montre un code dans Python langue utiliser la méthode du tamis pour trouver les facteurs premiers d’un nombre donné.

import math
High = (int)(1e5+7)
array=[0 for i in range(High)]
# function to generate all the smallest prime 
def Sieve():
#factors of the numbers until the maximum  number
    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):
#We will keep dividing until we reach 1
    if n == 1:
        return
    print((int)(array[n]))
    PrimeFactors((int)(n/array[n]))
#Here we call the function after dividing it by this prime
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

C'est la même solution que celle itérative de python mais écrite en Langage C.

On demande à l'utilisateur de saisir le nombre, puis pour chaque nombre de 2 à la racine carrée de ce nombre, il faut vérifier s'il est divisible en imprimant toutes les occurrences de ce facteur.

#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

C'est la même solution que la solution récursive python mais écrite en C.

Nous pouvons demander à l'utilisateur de saisir le numéro ; ensuite, nous construisons le tableau des nombres premiers qui stocke le plus petit facteur premier de chaque nombre. Enfin, nous appelons la fonction récursive Facteurs Premiers, qui divise le nombre donné par son plus petit facteur premier et se rappelle jusqu'à atteindre un.

#include <stdio.h>
int Max = 100007;
int array[100007];
void Sieve()//helping function to generate all the smallest //prime factors of the numbers until the maximum number
{
    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)//keep dividing until we reach 1
    {
        return;
    }
    printf("%d\n",array[n]);
    PrimeFactors(n/array[n]);//call the function after dividing by //this prime
}
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

• L’un des faits les plus intéressants est que tout nombre pair autre que 2 peut être la somme de deux nombres premiers.
• Par exemple : 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3…etc.
• Un autre fait est qu’il n’y a pas de nombres premiers consécutifs autres que 2 et 3, car le seul nombre premier pair est le nombre 2.
• Aussi, tous les nombres premiers sauf 2 et 3 peuvent s'écrire sous la forme suivante : 6 * n + 1 ou 6 * n – 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 factorisation première des nombres peut aider à résoudre des problèmes tels que la divisibilité, la simplification des fractions et la recherche de dénominateurs communs de différentes fractions.
• En outre, l’une des utilisations intéressantes de la factorisation première consiste à briser les codes secrets basés sur des nombres.