Comment trouver le plus grand facteur premier d'un nombre en Python ?

Trouver des facteurs premiers en Python

Une tâche courante en théorie des nombres est de trouver les facteurs premiers d'un nombre. Une méthode potentielle consiste simplement à diviser le nombre par un nombre sur deux de 2 jusqu'au plancher de sa racine carrée, en vérifiant si le reste est 0. Cependant, cette approche peut être coûteuse en calcul.

Une brute plus efficace- L'algorithme de force spécifiquement destiné à trouver le plus grand facteur premier d'un nombre est présenté ci-dessous :

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

Cet algorithme fonctionne en itérant sur tous les nombres jusqu'à la racine carrée du nombre donné. Pour chaque nombre, il vérifie si le nombre est un facteur du nombre donné et divise le nombre par le facteur si c'est le cas. L'algorithme continue jusqu'à ce que le nombre ne soit plus divisible par aucun des nombres de la plage et que le nombre restant soit le plus grand facteur premier.

<code class="python">largest_prime_factor(600851475143)
# Output: 6857

Alternativement, pour trouver tous les facteurs premiers d'un nombre :

<code class="python">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</code>

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!