Algorithmus zum Finden des größten Primfaktors einer Zahl

Was ist der beste Ansatz zur Berechnung des größten Primfaktors einer Zahl?

Ich denke, das effizienteste wäre das Folgende:

1. Finden Sie die niedrigste Primzahl, die sich sauber teilt
2. Überprüfen Sie, ob das Ergebnis der Teilung prim ist
3. Wenn nicht, finden Sie den nächstniedrigeren
4. Gehe zu 2.

Ich gehe davon aus, dass es einfacher ist, die kleinen Primfaktoren zu berechnen. Ist das ungefähr richtig? Welche anderen Ansätze sollte ich prüfen?

Bearbeiten: Ich habe jetzt erkannt, dass mein Ansatz zwecklos ist, wenn mehr als 2 Primfaktoren im Spiel sind, da Schritt 2 fehlschlägt, wenn das Ergebnis ein Produkt von zwei anderen Primzahlen ist, weshalb ein rekursiver Algorithmus benötigt wird.

Nochmals bearbeiten: Und jetzt habe ich festgestellt, dass dies immer noch funktioniert, da die zuletzt gefundene Primzahl die höchste sein muss. Daher würde jedes weitere Testen des Nicht-Primergebnisses aus Schritt 2 zu einer kleineren Primzahl führen.

Tatsächlich gibt es mehrere effizientere Möglichkeiten, um Faktoren mit großen Zahlen zu finden (für kleinere funktioniert die Testabteilung recht gut).

Eine Methode, die sehr schnell ist, wenn die Eingangszahl zwei Faktoren hat, die sehr nahe an ihrer Quadratwurzel liegen, ist als Fermat-Faktorisierung bekannt . Es nutzt die Identität N = (a + b) (a - b) = a ^ 2 - b ^ 2 und ist leicht zu verstehen und zu implementieren. Leider ist es im Allgemeinen nicht sehr schnell.

Die bekannteste Methode zum Faktorisieren von Zahlen mit einer Länge von bis zu 100 Stellen ist das quadratische Sieb . Als Bonus kann ein Teil des Algorithmus problemlos parallel verarbeitet werden.

Ein weiterer Algorithmus, von dem ich gehört habe, ist Pollards Rho-Algorithmus . Es ist nicht so effizient wie das quadratische Sieb im Allgemeinen, scheint aber einfacher zu implementieren zu sein.

Nachdem Sie sich entschieden haben, wie eine Zahl in zwei Faktoren aufgeteilt werden soll, finden Sie hier den schnellsten Algorithmus, den ich mir vorstellen kann, um den größten Primfaktor einer Zahl zu finden:

Erstellen Sie eine Prioritätswarteschlange, in der zunächst die Nummer selbst gespeichert wird. Bei jeder Iteration entfernen Sie die höchste Zahl aus der Warteschlange und versuchen, sie in zwei Faktoren aufzuteilen (wobei 1 natürlich nicht einer dieser Faktoren sein darf). Wenn dieser Schritt fehlschlägt, ist die Zahl eine Primzahl und Sie haben Ihre Antwort! Andernfalls fügen Sie die beiden Faktoren in die Warteschlange ein und wiederholen.

Hier ist der beste Algorithmus, den ich kenne (in 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

Die obige Methode wird im O(n)schlimmsten Fall ausgeführt (wenn die Eingabe eine Primzahl ist).

BEARBEITEN:
Unten ist die O(sqrt(n))Version, wie im Kommentar vorgeschlagen. Hier ist noch einmal der Code.

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

Meine Antwort basiert auf der von Triptychon , verbessert sich aber erheblich. Es basiert auf der Tatsache, dass nach 2 und 3 alle Primzahlen die Form 6n-1 oder 6n + 1 haben.

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

Ich habe kürzlich einen Blog-Artikel geschrieben erklärt wird, wie dieser Algorithmus funktioniert.

Ich würde es wagen, dass eine Methode, bei der kein Primalitätstest (und keine Siebkonstruktion) erforderlich ist, schneller abläuft als eine, bei der diese verwendet werden. Wenn dies der Fall ist, ist dies hier wahrscheinlich der schnellste Algorithmus.

JavaScript-Code:

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

Anwendungsbeispiel:

let result = largestPrimeFactor(600851475143);

Hier ist ein Beispiel für den Code :

Ähnlich wie @Triptych Antwort, aber auch anders. In diesem Beispiel wird eine Liste oder ein Wörterbuch nicht verwendet. Code ist in Ruby geschrieben

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

Alle Zahlen können als Produkt von Primzahlen ausgedrückt werden, z.

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

Sie können diese finden, indem Sie einfach bei 2 beginnen und einfach weiter teilen, bis das Ergebnis kein Vielfaches Ihrer Zahl ist:

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

Mit dieser Methode müssen Sie keine Primzahlen berechnen: Es handelt sich bei allen um Primzahlen, da Sie die Zahl bereits mit allen vorhergehenden Zahlen so weit wie möglich faktorisiert haben.

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
    }

Die einfachste Lösung ist ein Paar gegenseitig rekursiver Funktionen.

Die erste Funktion generiert alle Primzahlen:

1. Beginnen Sie mit einer Liste aller natürlichen Zahlen größer als 1.
2. Entfernen Sie alle Zahlen, die keine Primzahlen sind. Das heißt, Zahlen, die keine Primfaktoren haben (außer sich selbst). Siehe unten.

Die zweite Funktion gibt die Primfaktoren einer bestimmten Zahl nin aufsteigender Reihenfolge zurück.

1. Nehmen Sie eine Liste aller Primzahlen (siehe oben).
2. Entfernen Sie alle Zahlen, die keine Faktoren sind n.

Der größte Primfaktor von nist die letzte durch die zweite Funktion gegebene Zahl.

Dieser Algorithmus erfordert eine Lazy List oder eine Sprache (oder Datenstruktur) mit Call-by-Need- Semantik.

Zur Verdeutlichung ist hier eine (ineffiziente) Implementierung der oben genannten in 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

Um dies schneller zu machen, muss man nur klüger erkennen, welche Zahlen Primzahlen und / oder Faktoren sind n, aber der Algorithmus bleibt derselbe.

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)

Es gibt einige Modulo-Tests, die überflüssig sind, da n niemals durch 6 geteilt werden kann, wenn alle Faktoren 2 und 3 entfernt wurden. Sie können nur Primzahlen für i zulassen, was in mehreren anderen Antworten hier gezeigt wird.

Sie könnten das Sieb von Eratosthenes hier tatsächlich verflechten:

• Erstellen Sie zunächst die Liste der Ganzzahlen bis zu sqrt (n).
• Markieren Sie in der for-Schleife alle Vielfachen von i bis zum neuen sqrt (n) als nicht prim und verwenden Sie stattdessen eine while-Schleife.
• setze i auf die nächste Primzahl in der Liste.

Siehe auch diese Frage .

Mir ist bewusst, dass dies keine schnelle Lösung ist. Posting als hoffentlich leichter verständliche langsame Lösung.

 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 Iterativer Ansatz durch Entfernen aller Primfaktoren aus der Zahl

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

Ich verwende einen Algorithmus, der die Zahl weiterhin durch den aktuellen Primfaktor dividiert.

Meine Lösung in 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()))) 

Eingabe: 10 Ausgabe:5

Eingabe: 600851475143 Ausgabe:6857

Hier ist mein Versuch in c #. Der letzte Ausdruck ist der größte Primfaktor der Zahl. Ich habe nachgesehen und es funktioniert.

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

Berechnet den größten Primfaktor einer Zahl mithilfe der Rekursion in C ++. Die Funktionsweise des Codes wird nachfolgend erläutert:

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
}

Hier ist mein Ansatz, um schnell den größten Primfaktor zu berechnen. Es basiert auf der Tatsache, dass modifiziert xkeine Nicht-Primfaktoren enthält. Um dies zu erreichen, teilen wir, xsobald ein Faktor gefunden wird. Dann müssen Sie nur noch den größten Faktor zurückgeben. Es wäre schon Prime.

Der 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

Der folgende C ++ - Algorithmus ist nicht der beste, funktioniert jedoch für Zahlen unter einer Milliarde und ist ziemlich schnell

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

Fand diese Lösung im Web von "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;
}

Primfaktor mit Sieb:

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

Es scheint mir, dass Schritt 2 des angegebenen Algorithmus kein allzu effizienter Ansatz sein wird. Sie haben keine vernünftige Erwartung, dass es Prime ist.

Auch die vorherige Antwort, die das Sieb des Eratosthenes vorschlägt, ist völlig falsch. Ich habe gerade zwei Programme mit dem Faktor 123456789 geschrieben. Eines basierte auf dem Sieb, eines auf dem folgenden:

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

Diese Version war 90x schneller als das Sieb.

Die Sache ist, auf modernen Prozessoren ist die Art der Operation weitaus weniger wichtig als die Anzahl der Operationen, ganz zu schweigen davon, dass der obige Algorithmus im Cache ausgeführt werden kann, das Sieve nicht. Das Sieb verwendet viele Operationen, um alle zusammengesetzten Zahlen zu streichen.

Beachten Sie auch, dass meine Aufteilung der identifizierten Faktoren den zu testenden Speicherplatz verringert.

Berechnen Sie zuerst eine Liste, in der Primzahlen gespeichert sind, z. B. 2 3 5 7 11 13 ...

Verwenden Sie jedes Mal, wenn Sie eine Zahl mit Primzahlen faktorisieren, die Implementierung von Triptychon, wiederholen Sie jedoch diese Liste mit Primzahlen und nicht mit natürlichen ganzen Zahlen.

Mit Java:

Für intWerte:

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

Für longWerte:

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

Dies ist wahrscheinlich nicht immer schneller, aber optimistischer, wenn Sie einen großen Hauptteiler finden:

1. N ist deine Nummer
2. Wenn es Prime ist, dann return(N)
3. Berechnen Sie die Primzahlen bis Sqrt(N)
4. Gehen Sie die Primzahlen in absteigender Reihenfolge durch (größte zuerst)
   • Wenn N is divisible by PrimedannReturn(Prime)

Bearbeiten: In Schritt 3 können Sie das Sieb von Eratosthenes oder das Sieb von Atkins oder was auch immer Sie möchten verwenden, aber das Sieb allein wird Sie nicht als den größten Hauptfaktor finden. (Deshalb würde ich den Beitrag von SQLMenace nicht als offizielle Antwort wählen ...)

Ich denke, es wäre gut, alle möglichen Primzahlen, die kleiner als n sind, irgendwo zu speichern und sie einfach zu durchlaufen, um den größten Teiler zu finden. Sie können Primzahlen von prime-numbers.org erhalten .

Natürlich gehe ich davon aus, dass deine Nummer nicht zu groß ist :)

Nicht das schnellste, aber es funktioniert!

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

Hier ist die gleiche Funktion @ Triptychon als Generator vorgesehen, die ebenfalls leicht vereinfacht wurde.

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

Die maximale Primzahl kann dann ermittelt werden mit:

n= 373764623
max(primes(n))

und eine Liste von Faktoren, die gefunden wurden mit:

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