Wie kann ich testen für primality?
https://stackoverflow.com/questions/627463
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich bin eine kleine Bibliothek mit einigen Primzahl bezogenen Methoden zu schreiben. Wie ich den Grundstein getan haben (auch bekannt als Arbeitsmethoden) und seit einiger Optimierung ich suche. Natürlich steht das Internet ist ein ausgezeichneter Ort, dies zu tun. Ich habe jedoch stolperte über eine Rundung Problem, und ich habe mich gefragt, wie diese zu lösen.
In der Schleife verwende ich eine Nummer zu testen, es ist primality es effizienter ist, bis sqrt (n) anstelle von n / 2 oder sogar suchen n - 1. Aber aufgrund von Problemen eine bestimmte Anzahl Runden bekommen übersprungenen und damit einige Primzahlen übersprungen! Zum Beispiel sollte der 10000. Primzahl: 104.729, aber die ‚optimierte‘ Version endet mit:. 103811
Einige Code (es ist für mehr Optimierung offen, ich weiß, aber ich kann immer nur eine Sache handhaben):
/// <summary>
/// Method for testing the primality of a number e.g.: return IsPrime(29);
/// History:
/// 1. Initial version, most basic form of testing: m smaller then n -1
/// 2. Implemented m smaller then sqrt(n), optimization due to prime factoring
/// </summary>
/// <param name="test">Number to be tested on primality</param>
/// <returns>True if the number is prime, false otherwise</returns>
public static bool IsPrime(int test)
{
// 0 and 1 are not prime numbers
if (test == 0 || test == 1) return false;
// 2 and 3 are prime numbers
if (test == 2) return true;
// all even numbers, save 2, are not prime
if (test % 2 == 0) return false;
double squared = Math.Sqrt(test);
int flooredAndSquared = Convert.ToInt32(Math.Floor(squared));
// start with 5, make increments of 2, even numbers do not need to be tested
for (int idx = 3; idx < flooredAndSquared; idx++)
{
if (test % idx == 0)
{
return false;
}
}
return true;
}
Ich weiß, dass der eckige Teil versagt mich (oder ich nicht), versuchte Math.Ceiling auch, mit etwa den gleichen Ergebnissen.
Lösung
Leider habe ich vor den algorithmischen Ansätze nicht versucht. Aber wenn Sie möchten, dass Ihr Ansatz effizient implementieren, würde ich vorschlagen, einige Caching zu tun. Erstellen Sie ein Array speichern alle Primzahlen kleiner als eine definierte Schwelle, füllen Sie dieses Array, und die Suche innerhalb / es zu benutzen.
Im folgende Beispiel finden, ob eine Zahl prim ist O (1) im besten Fall (nämlich dann, wenn die Zahl kleiner als oder gleich maxPrime, die 821.461 für einen 64K-Puffer) und ein wenig optimierte für andere Fälle (von mod nur über 64K Zahlen aus dem ersten 820.000 Kontrolle - ca. 8%).
(Anmerkung:.. Nehmen Sie nicht diese Antwort als „optimal“ Ansatz Es ist eher ein Beispiel dafür, wie Ihre Implementierung zu optimieren)
public static class PrimeChecker
{
private const int BufferSize = 64 * 1024; // 64K * sizeof(int) == 256 KB
private static int[] primes;
public static int MaxPrime { get; private set; }
public static bool IsPrime(int value)
{
if (value <= MaxPrime)
{
return Array.BinarySearch(primes, value) >= 0;
}
else
{
return IsPrime(value, primes.Length) && IsLargerPrime(value);
}
}
static PrimeChecker()
{
primes = new int[BufferSize];
primes[0] = 2;
for (int i = 1, x = 3; i < primes.Length; x += 2)
{
if (IsPrime(x, i))
primes[i++] = x;
}
MaxPrime = primes[primes.Length - 1];
}
private static bool IsPrime(int value, int primesLength)
{
for (int i = 0; i < primesLength; ++i)
{
if (value % primes[i] == 0)
return false;
}
return true;
}
private static bool IsLargerPrime(int value)
{
int max = (int)Math.Sqrt(value);
for (int i = MaxPrime + 2; i <= max; i += 2)
{
if (value % i == 0)
return false;
}
return true;
}
}
Andere Tipps
Ich denke, das ist Ihr Problem:
for (int idx = 3; idx < flooredAndSquared; idx++)
Dies sollte
for (int idx = 3; idx <= flooredAndSquared; idx++)
so dass Sie nicht Quadratzahlen als Primzahlen. Sie können aber auch „idx + = 2“ statt verwenden „idx ++“, weil Sie nur ungerade Zahlen testen (wie Sie in den Kommentar schrieb direkt über ...).
Ich weiß nicht, ob dies ist genau, was Sie suchen, aber wenn Sie über die Geschwindigkeit wirklich besorgt sind, dann sollten Sie probablistic Methoden zum Testen primality Blick in anstatt mit einem Sieb. Rabin-Miller ein probabilistischer Primzahltest von Mathematica verwendet wird.
Ich stellte eine Klasse, die das Sieb oder Eratosthenes verwendet hier Primzahlen zu berechnen:
Ist die Größe eines Arrays durch die obere Grenze von int eingeschränkt (2147483647)?
Wie Mark sagte, der Miller-Rabin-Test ist eigentlich ein sehr guter Weg zu gehen. Eine zusätzliche Referenz (mit Pseudo-Code) ist der Wikipedia Artikel über es.
Es ist zu beachten, dass, während es probabilistischen ist, durch das Testen nur eine sehr geringe Anzahl von Fällen können Sie bestimmen, ob eine Zahl für Zahlen in den int Primzahl ist (und fast lang) Bereich. Siehe diesem Teil der Wikipedia-Artikel oder die Primality Proving Referenz für weitere Details.
Ich würde auch empfehlen dieser Artikel auf modulare Potenzierung, da sonst du gehst sehr mit sehr großen Zahlen zu tun hat, wenn den Miller-Rabin-Test zu tun versuchen ...
Sie könnte aussehen wollen in Fermats kleinen Satz .
Hier ist der Pseudo-Code aus dem Buch Algorithmen von S. Dasgupta, C. H. Papadimitriou und U. V. Vazirani , wobei n die Nummer, die Sie für den Primzahltest werden.
Pick a positive integer a < n at random
if a^n-1 is equivalent to 1 (mod n)
return yes
else
return no
sollte schneller als das Sieb Lösung sein Satz von Fermat Implementierung. Allerdings gibt es Carmichael Zahlen, die Fermat-Test und nicht prim passieren. Es gibt Abhilfen für diese. Ich empfehle Beratung Abschnitt 1.3 in den Vordergrund Buch erwähnt. Es geht um Primtests und könnte für Sie hilfreich sein.
Try this ...
if (testVal == 2) return true;
if (testVal % 2 == 0) return false;
for (int i = 3; i <= Math.Ceiling(Math.Sqrt(testVal)); i += 2)
{
if (testVal % i == 0)
return false;
}
return true;
Ive verwendet, um dies ein paar Mal recht .. Nicht so schnell wie ein Sieb .. aber es funktioniert.
Hier ist eine halbwegs anständige Funktion schrieb ich eine der Euler zu lösen:
private static long IsPrime(long input)
{
if ((input % 2) == 0)
{
return 2;
}
else if ((input == 1))
{
return 1;
}
else
{
long threshold = (Convert.ToInt64(Math.Sqrt(input)));
long tryDivide = 3;
while (tryDivide < threshold)
{
if ((input % tryDivide) == 0)
{
Console.WriteLine("Found a factor: " + tryDivide);
return tryDivide;
}
tryDivide += 2;
}
Console.WriteLine("Found a factor: " + input);
return -1;
}
}
Ich habe einen schnellen Algorithmus für die Überprüfung Primzahlen. Sie können Ihren Algorithmus verbessern, wenn Sie wissen, dass Primzahlen in der Form sind 6k ± 1, mit Ausnahme von 2 und 3. Also, zunächst können Sie testen, ob Eingabe von 2 oder 3 teilbar ist Dann lassen Sie die Zahl der Form 6k ± 1 ≤ √input.
bool IsPrime(int input)
{
//2 and 3 are primes
if (input == 2 || input == 3)
return true;
else if (input % 2 == 0 || input % 3 == 0)
return false; //Is divisible by 2 or 3?
else
{
for (int i = 5; i * i <= input; i += 6)
{
if (input % i == 0 || input % (i + 2) == 0)
return false;
}
return true;
}
}
Versuchen Sie, die Sieb des Eratosthenes - das nehmen sollte die Wurzel immer und Floating-Point Fragen.
Wie für die floor, werden Sie besser, indem man die ceiling serviert werden.
private static bool IsPrime(int number) {
if (number <= 3)
return true;
if ((number & 1) == 0)
return false;
int x = (int)Math.Sqrt(number) + 1;
for (int i = 3; i < x; i += 2) {
if ((number % i) == 0)
return false;
}
return true;
}
Ich kann es nicht bekommen schneller ...
Ich dachte, Primzahlen und Primzahltest war nützlich und klingt der AKS-Algorithmus interessant, auch wenn es nicht besonders praktisch ist, ein probabily basierten Tests im Vergleich zu.
Das funktioniert sehr schnell zum Testen Primzahlen (vb.net)
Dim rnd As New Random()
Const one = 1UL
Function IsPrime(ByVal n As ULong) As Boolean
If n Mod 3 = 0 OrElse n Mod 5 = 0 OrElse n Mod 7 = 0 OrElse n Mod 11 = 0 OrElse n Mod 13 = 0 OrElse n Mod 17 = 0 OrElse n Mod 19 = 0 OrElse n Mod 23 = 0 Then
return false
End If
Dim s = n - one
While s Mod 2 = 0
s >>= one
End While
For i = 0 To 10 - 1
Dim a = CULng(rnd.NextDouble * n + 1)
Dim temp = s
Dim m = Numerics.BigInteger.ModPow(a, s, n)
While temp <> n - one AndAlso m <> one AndAlso m <> n - one
m = (m * m) Mod n
temp = temp * 2UL
End While
If m <> n - one AndAlso temp Mod 2 = 0 Then
Return False
End If
Next i
Return True
End Function
Falls jemand interessiert ist, hier ist meine Umwandlung von Mohammed Verfahren oben zu VBA. Ich habe einen Scheck auszuschließen 1, 0, und negative Zahlen, da sie alle definiert als nicht prim sind.
Ich habe nur getestet diese in Excel VBA:
Function IsPrime(input_num As Long) As Boolean
Dim i As Long
If input_num < 2 Then '1, 0, and negative numbers are all defined as not prime.
IsPrime = False: Exit Function
ElseIf input_num = 2 Then
IsPrime = True: Exit Function '2 is a prime
ElseIf input_num = 3 Then
IsPrime = True: Exit Function '3 is a prime.
ElseIf input_num Mod 2 = 0 Then
IsPrime = False: Exit Function 'divisible by 2, so not a prime.
ElseIf input_num Mod 3 = 0 Then
IsPrime = False: Exit Function 'divisible by 3, so not a prime.
Else
'from here on, we only need to check for factors where
'6k ± 1 = square root of input_num:
i = 5
Do While i * i <= input_num
If input_num Mod i = 0 Then
IsPrime = False: Exit Function
ElseIf input_num Mod (i + 2) = 0 Then
IsPrime = False: Exit Function
End If
i = i + 6
Loop
IsPrime = True
End If
End Function
Ihr for-Schleife soll wie folgt aussehen:
for (int idx = 3; idx * idx <= test; idx++) { ... }
Auf diese Weise vermeiden Sie Fließkommaberechnung. Sollte schneller laufen und es wird genauer sein. Aus diesem Grunde bedingt die for Aussage ist einfach ein boolean Ausdruck:. Es Dinge wie dies möglich macht,
