Come posso verificare la primalità?
https://stackoverflow.com/questions/627463
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Sto scrivendo una piccola libreria con alcuni metodi relativi ai numeri primi. Come ho fatto le basi (alias metodi di lavoro) e ora sto cercando un po 'di ottimizzazione. Ovviamente Internet è un posto eccellente per farlo. Tuttavia, mi sono imbattuto in un problema di arrotondamento e mi chiedevo come risolverlo.
Nel ciclo che uso per testare un numero per la sua primalità è più efficiente cercare fino a sqrt (n) invece di n / 2 o anche n - 1. Ma a causa di problemi di arrotondamento alcuni numeri vengono saltati e quindi alcuni numeri primi sono saltato! Ad esempio, il 10000esimo primo dovrebbe essere: 104729, ma la versione "ottimizzata" finisce con: 103811.
Alcuni codici (è aperto per ulteriori ottimizzazioni, lo so, ma posso gestire solo una cosa alla volta):
/// <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;
}
So che la parte quadrata mi manca (o non ci riesco), ha provato anche Math.Ceiling, con gli stessi risultati.
Soluzione
Purtroppo, non ho mai provato gli approcci algoritmici prima. Ma se vuoi implementare il tuo approccio in modo efficiente, suggerirei di fare un po 'di cache. Crea un array per memorizzare tutti i numeri primi inferiori a una soglia definita, riempire questo array e cercare / utilizzarlo.
Nel seguente esempio, scoprire se un numero è primo è O (1) nel migliore dei casi (vale a dire, quando il numero è minore o uguale a maxPrime , che è 821.461 per un 64K buffer), ed è in qualche modo ottimizzato per altri casi (controllando la mod su solo 64 KB dei primi 820.000 - circa l'8%).
(Nota: non prendere questa risposta come approccio "ottimale". È più un esempio su come ottimizzare l'implementazione.)
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;
}
}
Altri suggerimenti
Immagino che questo sia il tuo problema:
for (int idx = 3; idx < flooredAndSquared; idx++)
Questo dovrebbe essere
for (int idx = 3; idx <= flooredAndSquared; idx++)
in modo da non ottenere numeri quadrati come numeri primi. Inoltre, puoi utilizzare " idx + = 2 " invece di " idx ++ " perché devi solo testare i numeri dispari (come hai scritto nel commento direttamente sopra ...).
Non so se questo è proprio quello che stai cercando, ma se sei veramente preoccupato per la velocità, dovresti cercare metodi probablistici per testare la primalità piuttosto che usare un setaccio. Rabin-Miller è un test probabilistico di primalità utilizzato da Mathematica.
Ho pubblicato una classe che utilizza il setaccio o Eratosthenes per calcolare i numeri primi qui:
La dimensione di un array è vincolata dal limite superiore di int (2147483647)?
Come ha detto Mark, il test di Miller-Rabin è in realtà un ottimo modo per procedere. Un riferimento aggiuntivo (con pseudo-codice) è articolo di Wikipedia su esso.
Va ??notato che mentre è probabilistico, testando solo un numero molto piccolo di casi, è possibile determinare se un numero è primo per i numeri nell'intervallo int (e quasi lungo). Vedi questa parte di quell'articolo di Wikipedia o il riferimento di Primality Proving per maggiori dettagli.
Consiglio anche di leggere questo articolo sull'esponenziazione modulare, altrimenti avere a che fare con numeri molto grandi quando si prova a fare il test di Miller-Rabin ...
Potresti voler esaminare il piccolo teorema di Fermat .
Ecco lo pseudo codice del libro Algorithms di S. Dasgupta, C.H. Papadimitriou e U.V. Vazirani , dove n è il numero che stai testando per la primalità.
Pick a positive integer a < n at random
if a^n-1 is equivalent to 1 (mod n)
return yes
else
return no
L'implementazione del teorema di Fermat dovrebbe essere più veloce della soluzione del setaccio. Tuttavia, ci sono numeri di Carmichael che superano il test di Fermat e NON sono primi. Ci sono soluzioni alternative per questo. Consiglio di consultare Sezione 1.3 del libro citato . Si tratta di test di primalità e potrebbe essere utile per te.
Prova questo ...
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;
L'ho usato parecchie volte .. Non veloce come un setaccio .. ma funziona.
Ecco una funzione decente a metà che ho scritto per risolvere uno degli Eulero:
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;
}
}
Ho un algoritmo veloce per controllare i numeri primi. Puoi migliorare il tuo algoritmo se sai che i numeri primi sono nella forma 6k ± 1, ad eccezione di 2 e 3. Quindi, prima puoi testare se l'input è divisibile per 2 o 3. Quindi, controlla tutti i numeri del modulo 6k ± 1 = vinput.
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;
}
}
Prova il setaccio di eratostene - che dovrebbe eliminare la radice e il virgola mobile problemi.
Per quanto riguarda il piano , sarai meglio servito prendendo il soffitto .
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;
}
Non riesco a ottenerlo più velocemente ...
Ho pensato Numeri primi e test di primalità è stato utile e l'algoritmo AKS sembra interessante anche se non è particolarmente pratico rispetto ai test basati su probabily.
Funziona molto velocemente per testare i numeri primi (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
Nel caso qualcuno fosse interessato, ecco la mia conversione della procedura di Mohammad sopra in VBA. Ho aggiunto un segno di spunta per escludere 1, 0 e numeri negativi poiché sono tutti definiti come non primi.
L'ho testato solo 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
Il tuo ciclo for dovrebbe assomigliare a questo:
for (int idx = 3; idx * idx <= test; idx++) { ... }
In questo modo, eviti il ??calcolo in virgola mobile. Dovrebbe correre più veloce e sarà più preciso. Questo è il motivo per cui l'istruzione for è semplicemente un'espressione booleana: rende possibili cose del genere.
