Comment un algorithme de force brute trouve-t-il le plus grand facteur premier d'un nombre, et pourquoi est-il plus rapide que de tester chaque nombre ?

Python trouvant des facteurs premiers

Question :

Question en deux parties :

1. Pouvez-vous expliquer comment fonctionne un algorithme de force brute pour trouver le plus grand facteur premier d'un nombre ?
2. Pourquoi cet algorithme est-il plus rapide que celui qui teste simplement chaque nombre ?

Exemple de code :

<code class="python">n = 600851475143
i = 2
while i * i < n:
    while n % i == 0:
        n = n / i
    i = i + 1

print(n)</code>

Réponse :

1. Comment fonctionne l'algorithme :

L'algorithme donné utilise la force brute pour trouver le plus grand facteur premier en parcourant tous les nombres de 2 jusqu'à la racine carrée du nombre n donné. Pour chaque nombre i, il vérifie s'il divise n sans reste. Si c’est le cas, il divise à plusieurs reprises n par i jusqu’à ce que n ne soit plus divisible par i. Il incrémente ensuite i de 1 et continue le processus. Le plus grand facteur premier sera la valeur finale de n.

2. Pourquoi l'algorithme est plus rapide :

L'algorithme donné est plus rapide que le simple test de chaque nombre car il profite du fait que tout facteur premier d'un nombre sera inférieur ou égal à sa racine carrée. En itérant uniquement jusqu'à la racine carrée de n, l'algorithme réduit le nombre de candidats potentiels à vérifier, améliorant considérablement son efficacité.

Algorithme amélioré :

L'algorithme fourni L'exemple de code présente des problèmes qui l'empêchent de trouver correctement le plus grand facteur premier dans tous les cas. Une version corrigée de l'algorithme est :

<code class="python">def largest_prime_factor(n):
    i = 2
    while i * i <= n:
        if n % i == 0:
            n //= i
        else:
            i += 1
    return n</code>

Cet algorithme trouve correctement le plus grand facteur premier, même pour les carrés parfaits et les nombres avec des facteurs premiers répétés.

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!