Wie funktioniert diese Methode, die den kleinsten Faktor einer bestimmten Zahl findet?

Question

ich vor kurzem über ein Verfahren gekommen sind, die den kleinsten Faktor einer bestimmten Zahl zurückgibt:

public static int findFactor(int n) 
{ 
    int i = 1; 

    int j = n - 1; 

    int p = j; // invariant: p = i * j 

    while(p != n && i < j) 
    { 
     i++; 
     p += j; 

     while(p > n) 
     { 
      j--; 
      p -= i; 
     } 
    } 

    return p == n ? i : n; 
} 

Nach der Methode der Prüfung, ich habe die Mengen (falsch höchstwahrscheinlich) in der Lage gewesen, festzustellen, welche einige ist Variablen repräsentieren jeweils:

n = the int that is subject to factorization for 
    the purposes of determining its smallest factor 

i = the next potential factor of n to be tested 

j = the smallest integer which i can be multiplied by to yield a value >= n 

Das Problem ist, ich weiß nicht, welche Menge p darstellt. Die innere Schleife scheint (p+=j) - n als ein potenzielles Vielfaches von i zu behandeln, aber gegeben, was ich glaube, j darstellt, verstehe ich nicht, wie das für alle i oder wie die äußere Schleife für die "zusätzliche" Iteration entfallen kann der inneren Schleife, die bevor dieser endet als Ergebnis p < n

Angenommen I richtig haben festgestellt, durchgeführt ist, was n, i und j repräsentieren, welche Menge sich p darstellen?

Wenn irgendeine meiner Bestimmungen falsch ist, was stellt jede der Mengen dar?

Answer 1

p steht für "Produkt". Die Invariante, wie angegeben, ist p == i*j; und der Algorithmus versucht verschiedene Kombinationen von i und j, bis das Produkt (p) n entspricht. Wenn dies nie der Fall ist (die while Schleife fällt durch), erhalten Sie p != n, und daher wird n zurückgegeben (n ist Prime).

Am Ende des äußeren Körpers while loop, j ist die größte ganze Zahl, die durch i multipliziert werden, um einen Wert ≤ n zu ergeben.

Der Algorithmus vermeidet eine explizite Division und versucht die Anzahl der j Werte zu begrenzen, die für jede i überprüft werden. Zu Beginn der äußeren Schleife ist p==i*j etwas weniger als n. Wie i schrittweise erhöht wird, muss allmählich schrumpfen. In jeder äußeren Schleife wird i erhöht (und p wird korrigiert, um der Invariante zu entsprechen). Die innere Schleife sinkt dann j (und korrigiert p), bis wieder ≤ n ist. Da i*j ist nur weniger als n zu Beginn der nächsten äußeren Schleife, erhöht i das Produkt größer als n wieder, und der Prozess wiederholt.

Answer 2

Der Algorithmus versucht alle Divisoren zwischen 1 und n/i (die Fortsetzung nach n/i ist nutzlos, da die entsprechenden Quotienten bereits ausprobiert wurden).

So ist die äußere Schleife führt tatsächlich

i= 1 
while i * (n/i) != n && i < n/i) 
{ 
    i++; 
} 

Es tut es auf eine kluge Art und Weise, durch Spaltungen zu vermeiden.Wie die Anmerkung sagt, wird die Invariante p = i * j beibehalten; genauer gesagt, ist das größte Vielfache von i, das n nicht überschreitet, und dies stellt tatsächlich j = n/i fest.

Es gibt eine kleine Anpassung auszuführen, wenn i erhöht wird: i immer i + 1 macht p = i * j(i + 1) * j = p + j geworden und p kann zu groß werden. Dies wird behoben, indem so oft wie nötig dekrementiert wird (j--, p-= i), um dies zu kompensieren.