Algorithmus zum Ermitteln des größten Primfaktors einer Zahl
https://stackoverflow.com/questions/23287
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Was ist der beste Ansatz zur Berechnung des größten Primfaktors einer Zahl?
Ich denke, am effizientesten wäre Folgendes:
- Finden Sie die niedrigste Primzahl, die sauber teilbar ist
- Prüfen Sie, ob das Divisionsergebnis eine Primzahl ist
- Wenn nicht, suchen Sie den nächstniedrigeren Wert
- Gehen Sie zu 2.
Ich stütze diese Annahme darauf, 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 sinnlos ist, wenn mehr als zwei Primfaktoren im Spiel sind, da Schritt 2 fehlschlägt, wenn das Ergebnis ein Produkt zweier anderer Primzahlen ist und daher ein rekursiver Algorithmus erforderlich ist.
Nochmal bearbeiten:Und jetzt ist mir klar geworden, dass das immer noch funktioniert, weil die zuletzt gefundene Primzahl die höchste sein muss und daher jede weitere Prüfung des Nicht-Primzahl-Ergebnisses aus Schritt 2 zu einer kleineren Primzahl führen würde.
Lösung
Tatsächlich gibt es mehrere effizientere Möglichkeiten, Faktoren großer Zahlen zu finden (bei kleineren funktioniert die Probedivision einigermaßen gut).
Eine Methode, die sehr schnell ist, wenn die Eingabezahl zwei Faktoren hat, die sehr nahe an ihrer Quadratwurzel liegen, heißt Fermat-Faktorisierung.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 Ziffern ist die Quadratisches Sieb.Als Bonus lässt sich ein Teil des Algorithmus problemlos durch Parallelverarbeitung realisieren.
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.
Sobald Sie sich entschieden haben, wie Sie eine Zahl in zwei Faktoren aufteilen, finden Sie hier den schnellsten Algorithmus, der mir einfällt, um den größten Primfaktor einer Zahl zu ermitteln:
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 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 den Vorgang.
Andere Tipps
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 ausgeführt O(n) im schlimmsten Fall (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 Triptychon's, verbessert es aber erheblich.Es basiert auf der Tatsache, dass alle Primzahlen jenseits von 2 und 3 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 geschrieben Blogartikel Erklären, wie dieser Algorithmus funktioniert.
Ich gehe davon aus, dass eine Methode, bei der kein Primzahltest (und keine Siebkonstruktion) erforderlich ist, schneller abläuft als eine Methode, die diese verwendet.Wenn das 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);
Alle Zahlen können als Produkt von Primzahlen ausgedrückt werden, z. B.:
102 = 2 x 3 x 17
712 = 2 x 2 x 2 x 89
Sie können diese ermitteln, indem Sie einfach bei 2 beginnen und einfach weiter dividieren, 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:Sie werden alle Primzahlen sein, basierend auf der Tatsache, dass Sie die Zahl bereits so weit wie möglich mit allen vorhergehenden Zahlen 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
}
Ähnlich wie die Antwort von @Triptych, aber auch anders.In diesem Beispiel wird weder eine Liste noch ein Wörterbuch verwendet.Der Code ist in Ruby geschrieben
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
Die einfachste Lösung ist ein Paar gegenseitig rekursiv Funktionen.
Die erste Funktion generiert alle Primzahlen:
- Beginnen Sie mit einer Liste aller natürlichen Zahlen größer als 1.
- 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 gegebenen Zahl zurück n in aufsteigender Reihenfolge.
- Machen Sie eine Liste aller Primzahlen (siehe oben).
- Entfernen Sie alle Zahlen, die keine Faktoren von sind
n.
Der größte Primfaktor von n ist die letzte von der zweiten Funktion angegebene Zahl.
Dieser Algorithmus erfordert a faule Liste oder eine Sprache (oder Datenstruktur) mit Anruf bei Bedarf Semantik.
Zur Verdeutlichung hier eine (ineffiziente) Implementierung des oben Gesagten 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 einfach besser erkennen, welche Zahlen Primzahlen und/oder Faktoren davon 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önnten für i nur Primzahlen zulassen, was in mehreren anderen Antworten hier gezeigt wird.
Hier könnte man tatsächlich das Sieb des Eratosthenes verflechten:
- Erstellen Sie zuerst die Liste der Ganzzahlen bis SQRT (n).
- In der für Schleifenmarke alle Vielfachen von I bis zum neuen SQRT (N) als nicht primär, und stattdessen eine Weile Loop verwenden.
- Setzen Sie I auf die nächste Primzahl in der Liste.
Siehe auch diese Frage.
Mir ist bewusst, dass dies keine schnelle Lösung ist.Posten 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;
}
Iterativer Python-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 ihren 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: 10Ausgabe : 5
Eingabe: 600851475143 Ausgabe : 6857
Hier ist mein Versuch in c#.Der letzte Ausdruck ist der größte Primfaktor der Zahl.Ich habe es überprüft 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 im Folgenden 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 zur schnellen Berechnung des größten Primfaktors.Es basiert auf Tatsachen, die geändert wurden x enthält keine Nicht-Primfaktoren.Um das zu erreichen, teilen wir x sobald ein Faktor gefunden wird.Dann bleibt nur noch die Rückgabe des größten Faktors.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 aber 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;
}
Habe diese Lösung im Internet gefunden 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 mittels 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 besonders effizienter Ansatz sein wird.Sie haben keine vernünftige Erwartung, dass es sich um eine Primzahl handelt.
Auch die vorherige Antwort, die auf das Sieb des Eratosthenes hinweist, ist völlig falsch.Ich habe gerade zwei Programme geschrieben, um 123456789 zu faktorisieren.Einer basierte auf dem Sieb, einer basierte auf Folgendem:
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 Sieve.
Tatsache ist, dass bei modernen Prozessoren die Art der Operation eine weitaus geringere Rolle spielt als die Anzahl der Operationen, ganz zu schweigen davon, dass der obige Algorithmus im Cache ausgeführt werden kann, das Sieve jedoch nicht.Das Sieb verwendet viele Operationen, um alle zusammengesetzten Zahlen zu streichen.
Beachten Sie außerdem, dass ich durch die Aufteilung der identifizierten Faktoren den zu testenden Raum verkleinere.
Berechnen Sie zunächst eine Liste, in der Primzahlen gespeichert sind, z. B.2 3 5 7 11 13 ...
Verwenden Sie jedes Mal, wenn Sie eine Zahl primfaktorisieren, die Implementierung von Triptych, iterieren Sie jedoch diese Liste von Primzahlen anstelle natürlicher Ganzzahlen.
Mit Java:
Für int Werte:
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 long Werte:
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 ist, dass Sie einen großen Primteiler finden:
Nist deine Nummer- Wenn es prim ist, dann
return(N) - Berechnen Sie die Primzahlen bis
Sqrt(N) - Gehen Sie die Primzahlen in absteigender Reihenfolge durch (größte zuerst)
- Wenn
N is divisible by PrimeDannReturn(Prime)
- Wenn
Bearbeiten:In Schritt 3 können Sie das Sieb des Eratosthenes oder das Sieb des Atkins oder was auch immer Sie möchten verwenden, aber das Sieb allein wird Ihnen nicht den größten Primfaktor 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 erhalten von prime-numbers.org.
Ich gehe natürlich davon aus, dass deine Zahl 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 wird die gleiche Funktion@Triptych als Generator bereitgestellt, die ebenfalls etwas 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 der Faktoren, die mithilfe von Folgendem ermittelt wurden:
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();
}
