Algorithmus zum Finden des größten Primfaktors einer Zahl

183

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.

mercutio
quelle
Mein Ansatz war: (1) große, mögliche Zahl durch 2 teilen; (2) prüfen, ob sich die große Zahl gleichmäßig darin teilt; (3) Wenn ja, prüfen Sie, ob die durch 2 geteilte Zahl eine Primzahl ist. Wenn ja, geben Sie es zurück. (4) Andernfalls subtrahieren Sie 1 von der durch 2 geteilten Zahl und kehren zu Schritt 3 zurück.
Kevin Meredith
1.Finden Sie eine Zahl, die sich klar teilt (für i = 2 bis int (sqr (num))), 2.dividieren Sie durch diese Zahl (num = num / i) und wiederholen Sie den 3.
Vorgang,
1
Wir können mit kleinen Primzahlen teilen, und diejenige, die schließlich übrig bleibt, ist der größte

Antworten:

134

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.

Artelius
quelle
3
Pollard Rho und die elliptische Kurvenmethode sind viel besser darin, kleine Primfaktoren Ihrer Zahl loszuwerden als das quadratische Sieb. QS hat ungefähr die gleiche Laufzeit, unabhängig von der Anzahl. Welcher Ansatz schneller ist, hängt von Ihrer Nummer ab. QS knackt schwer zu faktorisierende Zahlen schneller, während Rho und ECM leicht zu faktorisierende Zahlen schneller knacken.
tmyklebu
Vielen Dank für den Vorschlag zur quadratischen Variation. Ich musste dies für einen meiner Kunden implementieren. Die ursprüngliche Version, die ich entwickelte, entsprach den Vorschlägen von @mercutio in seiner Frage. Die quadratische Lösung ist das, was das Tool meines Kunden jetzt unter math.tools/calculator/prime-factors antreibt .
Dors
Wenn es eine effiziente Möglichkeit gibt, dieses Problem zu lösen, bedeutet das nicht, dass die Webverschlüsselung nicht sicher ist?
BKSpurgeon
141

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
Triptychon
quelle
11
Bitte lesen und / oder führen Sie diesen Code aus, bevor Sie ihn ablehnen. Es funktioniert gut. Einfach kopieren und einfügen. Wie geschrieben geben prime_factors (1000) [2,2,2,5,5,5] zurück, was als 2 ^ 3 * 5 ^ 3 interpretiert werden sollte, auch bekannt als Primfaktorisierung.
Triptychon
11
"läuft im O(sqrt(n))schlimmsten Fall ein" - Nein, es läuft im O(n)schlimmsten Fall ein (z n. B. wenn es Prime ist)
Sheldon L. Cooper
16
Es ist einfach, O (sqrt (n)) zu machen. Sie stoppen die Schleife einfach, wenn d * d> n ist. Wenn an dieser Stelle n> 1 ist, sollte ihr Wert an die Liste der Primfaktoren angehängt werden.
Sumudu Fernando
5
Gibt es einen Namen dafür?
Forethinker
11
Da 2 die einzige gerade Primzahl ist, können Sie anstelle von 1 jedes Mal separat für d = 2 iterieren und diese dann um 1 erhöhen. Ab d = 3 können Sie sie dann um 2 erhöhen. Dadurch wird die Zahl verringert von Iterationen ... :)
tailor_raj
18

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.

Sundar - Monica wieder einsetzen
quelle
12
Sie können diese Idee sogar noch weiter führen, z. B. über 2,3,5 hinaus haben alle Primzahlen die Form 30n + k (n> = 0), wobei k nur die Werte zwischen 1 und 29 annimmt, die nicht durch 2,3 teilbar sind oder 5, dh 7,11,13,17,19,23,29. Sie können dies sogar dynamisch nach jeweils wenigen gefundenen Primzahlen an 2 * 3 * 5 * 7 * ... * n + k anpassen lassen, wobei k durch keine dieser Primzahlen teilbar sein darf (beachten Sie, dass nicht alle möglichen k erforderlich sind Seien Sie Prime, zB für 210n + k müssen Sie 121 einschließen, sonst würden Sie 331 )
Tobias Kienzler
2
Ich denke, es sollte seinwhile (multOfSix - 1 <= n)
Nader Ghanbari
8

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 :

Vlad Bezden
quelle
7

Ä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
Ugnius Malūkas
quelle
Endlich etwas Lesbares und sofort (in js) ausführbares gleichzeitig. Ich habe versucht, eine unendliche Primliste zu verwenden, und bei 1 Million war sie bereits zu langsam.
Ebuall
4

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.
}
nickf
quelle
Ja, aber das ist schrecklich ineffizient. Sobald Sie alle 2s geteilt haben, sollten Sie wirklich nicht versuchen, durch 4 oder durch 6 oder ... zu teilen. Es ist wirklich viel effizienter, nur Primzahlen zu überprüfen oder einen anderen Algorithmus zu verwenden.
wnoise
6
+1, um wnoise auszugleichen, den ich für falsch halte. Der Versuch, durch 4 zu teilen, kommt nur einmal vor und schlägt sofort fehl. Ich denke nicht, dass das schlimmer ist, als 4 von einer Kandidatenliste zu entfernen, und es ist sicherlich schneller, als alle Primzahlen vorher zu finden.
Triptychon
2
@ Beowulf. Versuchen Sie, diesen Code auszuführen, bevor Sie abstimmen. Es gibt Primfaktoren zurück; Sie verstehen den Algorithmus einfach nicht.
Triptychon
3
Der Code funktioniert in Ordnung, ist aber langsam, wenn die eingehende Zahl eine Primzahl ist. Ich würde auch nur bis zum Quadrat laufen und um 2 erhöhen. Es könnte jedoch für sehr große Zahlen zu langsam sein.
blabla999
4
blabla999 ist genau richtig. Beispiel ist 1234567898766700 = 2 * 2 * 5 * 5 * 12345678987667. Wenn wir erreicht haben currFactor = 3513642, wissen wir, dass 12345678987667 eine Primzahl ist, und sollten sie als Antwort zurückgeben. Stattdessen setzt dieser Code die Aufzählung bis 12345678987667 selbst fort. Das ist 3.513.642x langsamer als nötig.
Will Ness
4
    //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
    }
the_prole
quelle
1
Haben Sie Ihren Code mit 1.000.000.000.039 ausprobiert? es sollte auch in einem Augenblick laufen. Macht es?
Will Ness
2
Sie könnten es im Voraus wissen, ohne es zu versuchen. 10 ^ 12 = (2 * 5) ^ 12 = 2 ^ 12 * 5 ^ 12. Ihre whileSchleife durchläuft also die iWerte von 2,2,2,2,2,2,2,2,2,2,2,2, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5. Alle 60 Iterationen. Aber für (10 ^ 12 + 39) gibt es (10 ^ 12 + 38) Iterationen i=2,3,4,5,6,...,10^12+39. Selbst wenn 10 ^ 10 Operationen eine Sekunde dauern, dauert 10 ^ 12 100 Sekunden. Aber es werden wirklich nur 10 ^ 6 Iterationen benötigt, und wenn 10 ^ 10 Operationen eine Sekunde dauern, würde 10 ^ 6 eine 1 / 10.000stel Sekunde dauern.
Will Ness
1
Weil ich nicht wusste, dass (10 ^ 12 + 39) eine Primzahl ist, die ich jetzt mache. Ich verstehe genau das, was du sagst.
the_prole
1
OK, Sie können Ihren Code so ändern, dass die Primzahlen nicht so stark verlangsamt werden: Wenn n = a b und a <= b, dann ist a a <= b a = n, dh a a <= n . Und wenn wir eine + 1 erreicht haben, dann ist n sicherlich eine Primzahl. (Pingen Sie mich an, wenn Sie Ihre Antwort bearbeiten, um dies aufzunehmen).
Will Ness
1
Was passiert wann long n = 2*1000000000039L? Funktioniert es so schnell wie es sollte? (Können Sie Ihren Code auch mithilfe einer return;Anweisung vereinfachen ?) (Wenn du willst, dass ich aufhöre, dich zu stupsen, sag es einfach;))
Will Ness
4

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.

Apocalisp
quelle
2
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 .

Ralph M. Rickenbach
quelle
2

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;
    } 
thejosh
quelle
1

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
Jyothir Aditya Singh
quelle
1

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

Kalpesh Dusane
quelle
0

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

  }
}
Seamus Barrett
quelle
0
#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
Rishabh Prasad
quelle
1
ist 25 der größte Primfaktor von 25?
Will Ness
0

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
}
4aRk Kn1gh7
quelle
0

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
Penkovsky
quelle
Aber wird dies nicht auch versuchen, mit allen geraden Zahlen zu teilen?
Janus Troelsen
0

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;
 }
sn
quelle
0

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;
}
BabarBaig
quelle
0

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;
}
Hautausschläge
quelle
-1

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.

Loren Pechtel
quelle
Das habe ich gesagt, wurde aber abgelehnt :( Ich denke, das Problem ist, dass wenn die Zahl einen wirklich großen Primfaktor hat (wie sich selbst), diese Methode bis zu dieser Zahl durchlaufen muss. In vielen Fällen Diese Methode ist jedoch recht effizient.
Nickf
Wenn Sie Ihre zurücklesen, ist es dasselbe, aber der erste Teil von Ihnen ist verwirrend.
Loren Pechtel
Versuchen Sie, dass auf dieser Nummer 143816789988504044536402352738195137863656439, lassen Sie mich wissen, wie effizient dies ist ...
MichaelICE
-1

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.

Guoger
quelle
-1

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;
}
Paul Vargas
quelle
-2

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 ...)

palotasb
quelle
1
Müssen Sie das Test-Factoring nicht durchführen, um festzustellen, ob es sich um eine Primzahl handelt (Schritt 2)? Denken Sie auch daran, den größten Primfaktor von 15 zu finden. Die Primzahlen bis sqrt (15) sind 2 und 3; aber der größte Primfaktor ist 5, nicht wahr? Ähnlich mit 20.
Jonathan Leffler
-3

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 :)

Klesk
quelle
-3

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;
    }
Nick
quelle
Dies ist keine Antwort auf die Frage. ;-) Die Frage war, den größten Primfaktor zu finden und nicht auf Primalität zu prüfen.
Hans-Peter Störr
Es ist viel effizienter, Ihre Schleife zu initialisieren als (long i = 3; i <checkUpTo; i + = 2)
cjk
-3

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))
pedram
quelle
-6
#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();
 }
Chitransh
quelle