Comment pouvez-vous optimiser l’algorithme de force brute pour trouver des facteurs premiers en Python ?

Trouver des facteurs premiers en Python : un guide complet

La détermination des facteurs premiers est une tâche fondamentale en théorie des nombres. Une approche pour trouver le plus grand facteur premier consiste à utiliser des algorithmes de force brute. Cependant, tous les algorithmes ne sont pas créés égaux.

Algorithme de force brute

Un algorithme couramment utilisé consiste à tester les nombres de manière incrémentielle jusqu'à ce qu'un nombre soit trouvé qui se divise uniformément dans l'original. nombre. Prenons un exemple de code :

n = 600851475143
i = 2
while i * i < n:
    while n % i == 0:
        n = n / i
    i = i + 1

print(n)

Ce code recherche le plus grand facteur premier de 600851475143. Cependant, il souffre d'inefficacité et prend environ 0,01 seconde.

Optimisé Algorithme de force brute

Une version améliorée de l'algorithme de force brute peut réduire considérablement le temps d'exécution :

def largest_prime_factor(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
    return n

Cet algorithme se termine dès que i dépasse la racine carrée de n , ce qui élimine efficacement le test de nombreux nombres inutiles. En conséquence, le temps d'exécution est considérablement réduit, s'exécutant en environ 388 microsecondes pour la même entrée.

Factorisation première complète

Si l'objectif est d'obtenir le nombre premier complet factorisation d'un nombre, une légère modification de l'algorithme est requise :

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

Cet algorithme maintient une liste appelée « facteurs » qui stocke les facteurs premiers au fur et à mesure qu'ils sont trouvés. Lorsque n est supérieur à 1 à la fin, il indique le facteur premier final, qui est ensuite ajouté à la liste.

En conclusion, choisir un algorithme de factorisation premier efficace est crucial pour les performances. L'algorithme de force brute optimisé offre une amélioration significative de la vitesse, tandis que l'algorithme de factorisation complet offre la factorisation première complète d'un nombre donné.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!