Algorithme pour trouver le plus grand facteur premier d'un nombre

Question

Quelle est la meilleure approche pour calculer le plus grand facteur premier d'un nombre ?

Je pense que la solution la plus efficace serait la suivante :

1. Trouver le plus petit nombre premier qui se divise proprement
2. Vérifier si le résultat de la division est premier
3. Si ce n'est pas le cas, trouver le niveau le plus bas.
4. Aller à 2.

Je me base sur le fait qu'il est plus facile de calculer les petits facteurs premiers. Est-ce à peu près exact ? Quelles autres approches devrais-je envisager ?

Edit : J'ai maintenant réalisé que mon approche est futile s'il y a plus de 2 facteurs premiers en jeu, puisque l'étape 2 échoue lorsque le résultat est un produit de deux autres facteurs premiers, et qu'un algorithme récursif est donc nécessaire.

Modifier à nouveau : J'ai maintenant réalisé que cela fonctionne toujours, car le dernier nombre premier trouvé doit être le plus élevé. Par conséquent, tout test ultérieur du résultat non premier de l'étape 2 aboutirait à un nombre premier plus petit.

Answer 1

Voici le meilleur algorithme que je connaisse (en Python)

def prime_factors(n):
    """Returns all the prime factors of a positive integer"""
    factors = []
    d = 2
    while n > 1:
        while n % d == 0:
            factors.append(d)
            n /= d
        d = d + 1

    return factors

pfs = prime_factors(1000)
largest_prime_factor = max(pfs) # The largest element in the prime factor list

La méthode ci-dessus s'exécute dans O(n) dans le pire des cas (lorsque l'entrée est un nombre premier).

EDIT :
Vous trouverez ci-dessous le O(sqrt(n)) comme suggéré dans le commentaire. Voici le code, une fois de plus.

def prime_factors(n):
    """Returns all the prime factors of a positive integer"""
    factors = []
    d = 2
    while n > 1:
        while n % d == 0:
            factors.append(d)
            n /= d
        d = d + 1
        if d*d > n:
            if n > 1: factors.append(n)
            break
    return factors

pfs = prime_factors(1000)
largest_prime_factor = max(pfs) # The largest element in the prime factor list

Answer 2

En fait, il existe plusieurs méthodes plus efficaces pour trouver les facteurs des grands nombres (pour les petits nombres, la division par essai fonctionne raisonnablement bien).

Une méthode très rapide si le nombre d'entrée a deux facteurs très proches de sa racine carrée est connue sous le nom de Factorisation de Fermat . Il utilise l'identité N = (a + b)(a - b) = a^2 - b^2 et est facile à comprendre et à mettre en œuvre. Malheureusement, il n'est pas très rapide en général.

La méthode la plus connue pour factoriser des nombres d'une longueur maximale de 100 chiffres est la méthode des Tamis quadratique . En prime, une partie de l'algorithme est facilement réalisable en traitement parallèle.

Un autre algorithme dont j'ai entendu parler est le suivant Algorithme Rho de Pollard . Il n'est pas aussi efficace que le crible quadratique en général, mais il semble plus facile à mettre en œuvre.

---

Une fois que vous avez décidé comment diviser un nombre en deux facteurs, voici l'algorithme le plus rapide auquel j'ai pensé pour trouver le plus grand facteur premier d'un nombre :

Créer une file d'attente prioritaire qui stocke initialement le numéro lui-même. À chaque itération, vous retirez le nombre le plus élevé de la file d'attente et tentez de le diviser en deux facteurs (sans permettre à 1 d'être l'un de ces facteurs, bien entendu). Si cette étape échoue, le nombre est premier et vous avez votre réponse ! Sinon, vous ajoutez les deux facteurs dans la file d'attente et vous recommencez.

Answer 3

Ma réponse est basée sur Triptyque mais l'améliore considérablement. Elle est basée sur le fait qu'au-delà de 2 et 3, tous les nombres premiers sont de la forme 6n-1 ou 6n+1.

var largestPrimeFactor;
if(n mod 2 == 0)
{
    largestPrimeFactor = 2;
    n = n / 2 while(n mod 2 == 0);
}
if(n mod 3 == 0)
{
    largestPrimeFactor = 3;
    n = n / 3 while(n mod 3 == 0);
}

multOfSix = 6;
while(multOfSix - 1 <= n)
{
    if(n mod (multOfSix - 1) == 0)
    {
        largestPrimeFactor = multOfSix - 1;
        n = n / largestPrimeFactor while(n mod largestPrimeFactor == 0);
    }

    if(n mod (multOfSix + 1) == 0)
    {
        largestPrimeFactor = multOfSix + 1;
        n = n / largestPrimeFactor while(n mod largestPrimeFactor == 0);
    }
    multOfSix += 6;
}

J'ai récemment écrit un article de blog expliquant le fonctionnement de cet algorithme.

J'ose espérer qu'une méthode ne nécessitant pas de test de primalité (ni de construction de tamis) fonctionnerait plus rapidement qu'une méthode utilisant ces tests. Si c'est le cas, il s'agit probablement de l'algorithme le plus rapide.

Answer 4

Similaire à la réponse de @Triptych mais aussi différente. Dans cet exemple, la liste ou le dictionnaire n'est pas utilisé. Le code est écrit en Ruby

def largest_prime_factor(number)
  i = 2
  while number > 1
    if number % i == 0
      number /= i;
    else
      i += 1
    end
  end
  return i
end

largest_prime_factor(600851475143)
# => 6857

Answer 5

Code JavaScript :

'option strict';

function largestPrimeFactor(val, divisor = 2) { 
    let square = (val) => Math.pow(val, 2);

    while ((val % divisor) != 0 && square(divisor) <= val) {
        divisor++;
    }

    return square(divisor) <= val
        ? largestPrimeFactor(val / divisor, divisor)
        : val;
}

Exemple d'utilisation :

let result = largestPrimeFactor(600851475143);

Voici un exemple de code :