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

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

Je pense que le plus efficace serait le suivant:

1. Trouver le plus petit nombre premier qui se divise proprement
2. Vérifiez si le résultat de la division est premier
3. Sinon, trouvez le plus bas suivant
4. Allez au 2.

Je fonde cette hypothèse sur le fait qu'il est plus facile de calculer les petits facteurs premiers. Est-ce à peu près correct? Quelles autres approches devrais-je examiner?

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 nombres premiers, donc un algorithme récursif est nécessaire.

Modifier à nouveau: Et maintenant, j'ai réalisé que cela fonctionnait toujours, car le dernier nombre premier trouvé doit être le plus élevé, donc tout test supplémentaire du résultat non premier de l'étape 2 entraînerait un nombre premier plus petit.

En fait, il existe plusieurs façons plus efficaces de trouver des facteurs de grand nombre (pour les plus petits, la division d'essai fonctionne raisonnablement bien).

Une méthode qui est très rapide si le nombre d'entrée a deux facteurs très proches de sa racine carrée est la 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, ce n'est pas très rapide en général.

La méthode la plus connue pour factoriser des nombres jusqu'à 100 chiffres est le tamis quadratique . En prime, une partie de l'algorithme se fait facilement avec un traitement parallèle.

Un autre algorithme dont j'ai entendu parler est l'algorithme Rho de Pollard . Ce n'est pas aussi efficace que le tamis quadratique en général, mais semble être plus facile à mettre en œuvre.

Une fois que vous avez décidé de diviser un nombre en deux facteurs, voici l'algorithme le plus rapide auquel je puisse penser pour trouver le plus grand facteur premier d'un nombre:

Créez une file d'attente prioritaire qui stocke initialement le numéro lui-même. À chaque itération, vous supprimez le nombre le plus élevé de la file d'attente et essayez de le diviser en deux facteurs (ne permettant pas à 1 d'être l'un de ces facteurs, bien sûr). 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 répétez.

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 fonctionne dans O(n)le pire des cas (lorsque l'entrée est un nombre premier).

EDIT:
Voici la O(sqrt(n))version, 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

Ma réponse est basée sur celle de Triptych , mais elle s'améliore beaucoup. Elle repose 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.

Je dirais qu'une méthode dans laquelle il n'est pas nécessaire de tester la primalité (et pas de construction de tamis) fonctionnerait plus rapidement qu'une méthode qui les utilise. Si tel est le cas, c'est probablement l'algorithme le plus rapide ici.

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 :

Similaire à la réponse @Triptych mais aussi différent. 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

Tous les nombres peuvent être exprimés comme le produit de nombres premiers, par exemple:

102 = 2 x 3 x 17
712 = 2 x 2 x 2 x 89

Vous pouvez les trouver en commençant simplement à 2 et en continuant simplement à diviser jusqu'à ce que le résultat ne soit pas un multiple de votre nombre:

712 / 2 = 356 .. 356 / 2 = 178 .. 178 / 2 = 89 .. 89 / 89 = 1

en utilisant cette méthode, vous n'avez pas à calculer réellement de nombres premiers: ils seront tous des nombres premiers, sur la base du fait que vous avez déjà factorisé le nombre autant que possible avec tous les nombres précédents.

number = 712;
currNum = number;    // the value we'll actually be working with
for (currFactor in 2 .. number) {
    while (currNum % currFactor == 0) {
        // keep on dividing by this number until we can divide no more!
        currNum = currNum / currFactor     // reduce the currNum
    }
    if (currNum == 1) return currFactor;    // once it hits 1, we're done.
}

    //this method skips unnecessary trial divisions and makes 
    //trial division more feasible for finding large primes

    public static void main(String[] args) 
    {
        long n= 1000000000039L; //this is a large prime number 
        long i = 2L;
        int test = 0;

        while (n > 1)
        {
            while (n % i == 0)
            {
                n /= i;     
            }

            i++;

            if(i*i > n && n > 1) 
            {
                System.out.println(n); //prints n if it's prime
                test = 1;
                break;
            }
        }

        if (test == 0)  
            System.out.println(i-1); //prints n if it's the largest prime factor
    }

La solution la plus simple est une paire de fonctions mutuellement récursives .

La première fonction génère tous les nombres premiers:

1. Commencez par une liste de tous les nombres naturels supérieurs à 1.
2. Supprimez tous les nombres qui ne sont pas premiers. Autrement dit, les nombres qui n'ont pas de facteurs premiers (autres qu'eux-mêmes). Voir ci-dessous.

La deuxième fonction renvoie les facteurs premiers d'un nombre donné ndans l'ordre croissant.

1. Prenez une liste de tous les nombres premiers (voir ci-dessus).
2. Supprimez tous les nombres qui ne sont pas des facteurs de n.

Le plus grand facteur premier de nest le dernier nombre donné par la deuxième fonction.

Cet algorithme nécessite une liste différée ou un langage (ou une structure de données) avec une sémantique d' appel par besoin .

Pour clarifier, voici une implémentation (inefficace) de ce qui précède dans Haskell:

import Control.Monad

-- All the primes
primes = 2 : filter (ap (<=) (head . primeFactors)) [3,5..]

-- Gives the prime factors of its argument
primeFactors = factor primes
  where factor [] n = []
        factor xs@(p:ps) n =
          if p*p > n then [n]
          else let (d,r) = divMod n p in
            if r == 0 then p : factor xs d
            else factor ps n

-- Gives the largest prime factor of its argument
largestFactor = last . primeFactors

Pour accélérer cela, il suffit d'être plus intelligent pour détecter les nombres premiers et / ou les facteurs de n, mais l'algorithme reste le même.

n = abs(number);
result = 1;
if (n mod 2 == 0) {
  result = 2;
  while (n mod 2 = 0) n /= 2;
}
for(i=3; i<sqrt(n); i+=2) {
  if (n mod i == 0) {
    result = i;
    while (n mod i = 0)  n /= i;
  }
}
return max(n,result)

Certains tests modulo sont superflus, car n ne peut jamais être divisé par 6 si tous les facteurs 2 et 3 ont été supprimés. Vous ne pouvez autoriser que les nombres premiers pour i, ce qui est indiqué dans plusieurs autres réponses ici.

Vous pourriez en fait entrelacer le tamis d'Eratosthène ici:

• Créez d'abord la liste d'entiers jusqu'à sqrt (n).
• Dans la boucle for, marquez tous les multiples de i jusqu'au nouveau sqrt (n) comme non premiers et utilisez une boucle while à la place.
• mettre i au nombre premier suivant de la liste.

Voir aussi cette question .

Je suis conscient que ce n'est pas une solution rapide. Poster comme solution lente, espérons-le plus facile à comprendre.

 public static long largestPrimeFactor(long n) {

        // largest composite factor must be smaller than sqrt
        long sqrt = (long)Math.ceil(Math.sqrt((double)n));

        long largest = -1;

        for(long i = 2; i <= sqrt; i++) {
            if(n % i == 0) {
                long test = largestPrimeFactor(n/i);
                if(test > largest) {
                    largest = test;
                }
            }
        }

        if(largest != -1) {
            return largest;
        }

        // number is prime
        return n;
    } 

Approche itérative Python en supprimant tous les facteurs premiers du nombre

def primef(n):
    if n <= 3:
        return n
    if n % 2 == 0:
        return primef(n/2)
    elif n % 3 ==0:
        return primef(n/3)
    else:
        for i in range(5, int((n)**0.5) + 1, 6):
            #print i
            if n % i == 0:
                return primef(n/i)
            if n % (i + 2) == 0:
                return primef(n/(i+2))
    return n

J'utilise un algorithme qui continue de diviser le nombre par son facteur premier actuel.

Ma solution en python 3:

def PrimeFactor(n):
    m = n
    while n%2==0:
        n = n//2
    if n == 1:         # check if only 2 is largest Prime Factor 
        return 2
    i = 3
    sqrt = int(m**(0.5))  # loop till square root of number
    last = 0              # to store last prime Factor i.e. Largest Prime Factor
    while i <= sqrt :
        while n%i == 0:
            n = n//i       # reduce the number by dividing it by it's Prime Factor
            last = i
        i+=2
    if n> last:            # the remaining number(n) is also Factor of number 
        return n
    else:
        return last
print(PrimeFactor(int(input()))) 

Entrée: 10 Sortie:5

Entrée: 600851475143 Sortie:6857

Voici ma tentative en c #. La dernière impression est le plus grand facteur premier du nombre. J'ai vérifié et ça marche.

namespace Problem_Prime
{
  class Program
  {
    static void Main(string[] args)
    {
      /*
       The prime factors of 13195 are 5, 7, 13 and 29.

      What is the largest prime factor of the number 600851475143 ?
       */
      long x = 600851475143;
      long y = 2;
      while (y < x)
      {
        if (x % y == 0)
        {
          // y is a factor of x, but is it prime
          if (IsPrime(y))
          {
            Console.WriteLine(y);
          }
          x /= y;
        }

        y++;

      }
      Console.WriteLine(y);
      Console.ReadLine();
    }
    static bool IsPrime(long number)
    {
      //check for evenness
      if (number % 2 == 0)
      {
        if (number == 2)
        {
          return true;
        }
        return false;
      }
      //don't need to check past the square root
      long max = (long)Math.Sqrt(number);
      for (int i = 3; i <= max; i += 2)
      {
        if ((number % i) == 0)
        {
          return false;
        }
      }
      return true;
    }

  }
}

#python implementation
import math
n = 600851475143
i = 2
factors=set([])
while i<math.sqrt(n):
   while n%i==0:
       n=n/i
       factors.add(i)
   i+=1
factors.add(n)
largest=max(factors)
print factors
print largest

Calcule le plus grand facteur premier d'un nombre à l'aide de la récursivité en C ++. Le fonctionnement du code est expliqué ci-dessous:

int getLargestPrime(int number) {
    int factor = number; // assumes that the largest prime factor is the number itself
    for (int i = 2; (i*i) <= number; i++) { // iterates to the square root of the number till it finds the first(smallest) factor
        if (number % i == 0) { // checks if the current number(i) is a factor
            factor = max(i, number / i); // stores the larger number among the factors
            break; // breaks the loop on when a factor is found
        }
    }
    if (factor == number) // base case of recursion
        return number;
    return getLargestPrime(factor); // recursively calls itself
}

Voici mon approche pour calculer rapidement le plus grand facteur premier. Il est basé sur le fait que modifié xne contient pas de facteurs non premiers. Pour y parvenir, nous nous divisons xdès qu'un facteur est trouvé. Ensuite, la seule chose qui reste est de renvoyer le plus grand facteur. Ce serait déjà prime.

Le code (Haskell):

f max' x i | i > x = max'
           | x `rem` i == 0 = f i (x `div` i) i  -- Divide x by its factor
           | otherwise = f max' x (i + 1)  -- Check for the next possible factor

g x = f 2 x 2

L'algorithme C ++ suivant n'est pas le meilleur, mais il fonctionne pour les nombres inférieurs à un milliard et c'est assez rapide

#include <iostream>
using namespace std;

// ------ is_prime ------
// Determines if the integer accepted is prime or not
bool is_prime(int n){
    int i,count=0;
    if(n==1 || n==2)
      return true;
    if(n%2==0)
      return false;
    for(i=1;i<=n;i++){
    if(n%i==0)
        count++;
    }
    if(count==2)
      return true;
    else
      return false;
 }
 // ------ nextPrime -------
 // Finds and returns the next prime number
 int nextPrime(int prime){
     bool a = false;
     while (a == false){
         prime++;
         if (is_prime(prime))
            a = true;
     }
  return prime;
 }
 // ----- M A I N ------
 int main(){

      int value = 13195;
      int prime = 2;
      bool done = false;

      while (done == false){
          if (value%prime == 0){
             value = value/prime;
             if (is_prime(value)){
                 done = true;
             }
          } else {
             prime = nextPrime(prime);
          }
      }
        cout << "Largest prime factor: " << value << endl;
 }

J'ai trouvé cette solution sur le Web par "James Wang"

public static int getLargestPrime( int number) {

    if (number <= 1) return -1;

    for (int i = number - 1; i > 1; i--) {
        if (number % i == 0) {
            number = i;
        }
    }
    return number;
}

Facteur principal utilisant un tamis:

#include <bits/stdc++.h>
using namespace std;
#define N 10001  
typedef long long ll;
bool visit[N];
vector<int> prime;

void sieve()
{
            memset( visit , 0 , sizeof(visit));
            for( int i=2;i<N;i++ )
            {
                if( visit[i] == 0)
                {
                    prime.push_back(i);
                    for( int j=i*2; j<N; j=j+i )
                    {
                        visit[j] = 1;
                    }
                }
            }   
}
void sol(long long n, vector<int>&prime)
{
            ll ans = n;
            for(int i=0; i<prime.size() || prime[i]>n; i++)
            {
                while(n%prime[i]==0)
                {
                    n=n/prime[i];
                    ans = prime[i];
                }
            }
            ans = max(ans, n);
            cout<<ans<<endl;
}
int main() 
{
           ll tc, n;
           sieve();

           cin>>n;
           sol(n, prime);

           return 0;
}

Il me semble que l'étape n ° 2 de l'algorithme donné ne sera pas une approche aussi efficace. Vous ne vous attendez pas à ce que ce soit le meilleur.

En outre, la réponse précédente suggérant le tamis d'Eratosthène est totalement fausse. Je viens d'écrire deux programmes au facteur 123456789. L'un était basé sur le tamis, l'autre était basé sur ce qui suit:

1)  Test = 2 
2)  Current = Number to test 
3)  If Current Mod Test = 0 then  
3a)     Current = Current Div Test 
3b)     Largest = Test
3c)     Goto 3. 
4)  Inc(Test) 
5)  If Current < Test goto 4
6)  Return Largest

Cette version était 90 fois plus rapide que le Sieve.

Le fait est que sur les processeurs modernes, le type d'opération importe beaucoup moins que le nombre d'opérations, sans compter que l'algorithme ci-dessus peut s'exécuter en cache, le Sieve ne le peut pas. Le tamis utilise de nombreuses opérations en supprimant tous les nombres composites.

Notez également que ma division des facteurs au fur et à mesure qu'ils sont identifiés réduit l'espace qui doit être testé.

Calculez d'abord une liste contenant des nombres premiers, par exemple 2 3 5 7 11 13 ...

Chaque fois que vous factorisez un nombre premier, utilisez l'implémentation de Triptych mais en itérant cette liste de nombres premiers plutôt que d'entiers naturels.

Avec Java:

Pour les intvaleurs:

public static int[] primeFactors(int value) {
    int[] a = new int[31];
    int i = 0, j;
    int num = value;
    while (num % 2 == 0) {
        a[i++] = 2;
        num /= 2;
    }
    j = 3;
    while (j <= Math.sqrt(num) + 1) {
        if (num % j == 0) {
            a[i++] = j;
            num /= j;
        } else {
            j += 2;
        }
    }
    if (num > 1) {
        a[i++] = num;
    }
    int[] b = Arrays.copyOf(a, i);
    return b;
}

Pour les longvaleurs:

static long[] getFactors(long value) {
    long[] a = new long[63];
    int i = 0;
    long num = value;
    while (num % 2 == 0) {
        a[i++] = 2;
        num /= 2;
    }
    long j = 3;
    while (j <= Math.sqrt(num) + 1) {
        if (num % j == 0) {
            a[i++] = j;
            num /= j;
        } else {
            j += 2;
        }
    }
    if (num > 1) {
        a[i++] = num;
    }
    long[] b = Arrays.copyOf(a, i);
    return b;
}

Ce n'est probablement pas toujours plus rapide mais plus optimiste quant au fait que vous trouvez un grand diviseur premier:

1. N est ton numéro
2. Si c'est le meilleur alors return(N)
3. Calculer les nombres premiers jusqu'à Sqrt(N)
4. Parcourez les nombres premiers par ordre décroissant (le plus grand en premier)
   • Si N is divisible by PrimealorsReturn(Prime)

Edit: À l'étape 3, vous pouvez utiliser le tamis d'Eratosthène ou le tamis d'Atkins ou tout ce que vous voulez, mais en lui-même, le tamis ne vous trouvera pas le plus grand facteur premier. (C'est pourquoi je ne choisirais pas le post de SQLMenace comme réponse officielle ...)

Pas le plus rapide mais ça marche!

    static bool IsPrime(long num)
    {
        long checkUpTo = (long)Math.Ceiling(Math.Sqrt(num));
        for (long i = 2; i <= checkUpTo; i++)
        {
            if (num % i == 0)
                return false;
        }
        return true;
    }

Voici la même fonction @ Triptyque fournie en générateur, qui a également été légèrement simplifiée.

def primes(n):
    d = 2
    while (n > 1):
        while (n%d==0):
            yield d
            n /= d
        d += 1

le max prime peut alors être trouvé en utilisant:

n= 373764623
max(primes(n))

et une liste de facteurs trouvés en utilisant:

list(primes(n))

Je pense qu'il serait bon de stocker quelque part tous les nombres premiers possibles plus petits que n et de simplement les parcourir pour trouver le plus grand diviseur. Vous pouvez obtenir des nombres premiers sur prime-numbers.org .

Bien sûr, je suppose que votre nombre n'est pas trop grand :)

#include<stdio.h>
#include<conio.h>
#include<math.h>
#include <time.h>

factor(long int n)
{
long int i,j;
while(n>=4)
 {
if(n%2==0) {  n=n/2;   i=2;   }

 else
 { i=3;
j=0;
  while(j==0)
  {
   if(n%i==0)
   {j=1;
   n=n/i;
   }
   i=i+2;
  }
 i-=2;
 }
 }
return i;
 }

 void main()
 { 
  clock_t start = clock();
  long int n,sp;
  clrscr();
  printf("enter value of n");
  scanf("%ld",&n);
  sp=factor(n);
  printf("largest prime factor is %ld",sp);

  printf("Time elapsed: %f\n", ((double)clock() - start) / CLOCKS_PER_SEC);
  getch();
 }