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

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

EDIT:

Voici la version 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

ma réponse est basée sur Triptyque 's, mais améliore beaucoup sur elle. Il est basé sur le fait qu'au-delà de 2 et 3, tous les nombres premiers 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 comment cet algorithme fonctionne.

je risquerais qu'une méthode dans laquelle il n'y a pas besoin d'un test pour la primalité (et aucune construction de tamis) fonctionnerait plus vite qu'un ce qui ne les utiliser. Si c'est le cas, c'est probablement l'algorithme le plus rapide ici.

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 n'est 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 des nombres premiers: ils seront tous des nombres premiers, basé sur le 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
    }

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 du code :

similaire à @Triptych réponse, 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;
      i -= 1
    end
    i += 1
  end
  return i
end

largest_prime_factor(600851475143)
# => 6857

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. commence par une liste qui se compose de 2 et de tous les nombres impairs supérieurs à 2.
2. supprimer tous les nombres qui ne sont pas premiers. Qui est, des chiffres qui n'ont pas de facteurs premiers (autres qu'eux-mêmes). Voir ci-dessous.

La seconde fonction retourne les facteurs premiers d'un nombre donné n dans l'ordre croissant. La stratégie est d'essayer de diviser n par chaque premier qui pourrait éventuellement être son diviseur:

1. prenez une liste de tous les nombres premiers dans l'ordre croissant (voir ci-dessus).
2. soit p soit un nombre premier dans cette liste, et ps soit les facteurs premiers de n/p (voir étape 1).
   • si p au carré est plus grand que notre nombre n , puis n est premier. Nous avons terminé.
   • si p divise n , alors p est un facteur principal de n . Les autres facteurs sont ps .
   • autrement p n'est pas un facteur principal de n .

le facteur principal le plus important de n est le dernier nombre donné par la deuxième fonction.

pour plus de précision, voici le code 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

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)

il y a des tests de modulo qui sont superflous, comme n ne peut jamais être divisé par 6 si tous les facteurs 2 et 3 ont été enlevés. Vous ne pouvez permettre que des nombres premiers pour i, ce qui est montré dans plusieurs autres réponses ici.

vous pourriez en fait entrelacer le tamis D'Eratosthène ici:

• créez D'abord la liste des entiers à sqrt(n).
• dans le marqueur de boucle for tous les multiples de i jusqu'à la nouvelle sqrt(n) ne pas le premier, et d'utiliser une boucle while à la place.
• fixe i au prochain nombre premier dans liste.

Voir aussi cette question .

je suis conscient que ce n'est pas une solution rapide. Affichage comme, espérons plus facile à comprendre solution lente.

 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;
    } 

Python approche Itérative par la suppression de 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 à diviser le nombre par son facteur principal 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 dans c#. La dernière impression est le facteur principal le plus important du nombre. J'ai vérifié et il fonctionne.

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 en utilisant la récursion 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 principal. Il est basé sur le fait que modifié x ne contient pas de facteurs non-prime. Pour y parvenir, nous diviser x dès qu'un facteur est trouvé. La seule chose qui reste est de rendre le plus grand facteur. Il serait déjà premier.

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 de moins d'un milliard et son 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;
 }

a 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;
}

le Premier facteur à l'aide de 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 2 de l'algorithme donné ne va pas du tout être efficace, une approche. Vous n'avez aucune attente raisonnable qu'il soit premier.

aussi, la réponse précédente suggérant le tamis D'Eratosthène est tout à fait fausse. Je viens d'écrire deux programmes de facteur 123456789. L'une était basée sur le tamis, l'autre était basée 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 90x plus rapide que le tamis.

Le fait est que, sur les processeurs modernes, le type d'opération importe beaucoup moins que le nombre d'opérations, sans mentionner que l'algorithme ci-dessus peut fonctionner en cache, le tamis ne peut pas. Le tamis utilise beaucoup d'opérations de suppression de tous les numéros composés.

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

calculer une liste stockant les nombres premiers en premier, par exemple 2 3 5 7 11 13 ...

chaque fois que vous prime factorisez un nombre, utilisez l'implémentation par Triptyque mais en itérant cette liste de nombres premiers plutôt que des entiers naturels.

Avec Java:

pour int valeurs:

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 long valeurs:

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 à propos de ce que vous trouvez un grand diviseur prime:

1. N est votre numéro
2. si elle est prime puis return(N)
3. calculer les primes jusqu'à Sqrt(N)
4. passer par les nombres premiers dans l'ordre décroissant (le plus grand premier)
   • si N is divisible by Prime puis Return(Prime)

Edit: dans l'étape 3, vous pouvez utiliser le tamis D'Eratosthène ou le tamis D'Atkins ou ce que vous voulez, mais par lui-même le tamis ne vous trouvera pas le plus grand facteur principal. (Thats pourquoi je ne choisirais pas le poste de SQLMenace comme une réponse officielle...)

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

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

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@Triptych fournie comme 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 des facteurs trouvés en utilisant:

list(primes(n))

#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();
 }