Come posso testare per la primalità?

Question

Sto scrivendo una piccola libreria con alcuni metodi relativi ai numeri primi. Come ho fatto il lavoro di base (ovvero i metodi di lavoro) e ora sto cercando qualche ottimizzazione. Ofcourse internet è un posto eccellente per farlo. Tuttavia, sono incappato in un problema di arrotondamento e mi chiedevo come risolvere questo problema.

Nel ciclo che utilizzo per testare un numero per la sua primalità è più efficiente cercare fino a sqrt (n) invece di n/2 o anche di n - 1. Ma a causa di problemi di arrotondamento alcuni numeri vengono saltati e quindi alcuni numeri primi sono saltati! Ad esempio, il 10000 primo dovrebbe essere: 104729, ma la versione "ottimizzata" termina con: 103811.

Un po 'di codice (è 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 quadrato me non riesce (o non riesco), provato Math.Ceiling pure, con gli stessi risultati.

Answer 1

Purtroppo, non ho ho provato prima gli approcci algoritmici. Ma se vuoi implementare il tuo approccio in modo efficiente, ti suggerisco di fare un po 'di cache. Creare una matrice per memorizzare tutti i numeri primi inferiori a una soglia definita, riempire questo array e cercare all'interno/utilizzarlo.

Nell'esempio seguente, la ricerca di un numero primo è O (1) nel caso migliore (vale a dire, quando il numero è minore o uguale a maxPrime, che è 821,461 per un buffer da 64 KB) ed è in qualche modo ottimizzato per altri casi (controllando mod su solo 64K numeri sui primi 820.000 - circa l'8%).

(NOTA:.. Non prendere questa risposta come l'approccio "ottimale" E 'più di 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; 
    } 
} 

Answer 2

Provate il sieve of eratosthenes - che dovrebbe risolvere i problemi di root e floating point.

Per quanto riguarda lo floor, sarà meglio servito prendendo il ceiling.

Answer 3

Ecco una funzione a metà strada decente che ho scritto per risolvere uno dei 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; 
    } 
} 

Answer 4

Credo che questo è il problema:

for (int idx = 3; idx < flooredAndSquared; idx++) 

Questo dovrebbe essere

for (int idx = 3; idx <= flooredAndSquared; idx++) 

quindi non ottieni numeri quadrati come numeri primi. Inoltre, puoi usare "idx + = 2" invece di "idx ++" perché devi solo testare numeri dispari (come hai scritto nel commento direttamente sopra ...).

Answer 5

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; 

Ive ha usato questo un bel paio di volte .. non così rapidamente come un setaccio .. ma funziona.

Answer 6

ho postato una classe che utilizza il setaccio o Eratostene per calcolare i numeri primi qui:

Is the size of an array constrained by the upper limit of int (2147483647)?

Answer 7

non so se questo è proprio quello che stai cercando, ma se siete veramente preoccupati allora dovresti esaminare i metodi probablistici per testare la primalità piuttosto che usare un setaccio. Rabin-Miller è un test di primitività probabilistico utilizzato da Mathematica.

Answer 8

vostro ciclo dovrebbe essere simile a questo:

for (int idx = 3; idx * idx <= test; idx++) { ... } 

In questo modo, a virgola mobile si evita di calcolo. Dovrebbe correre più veloce e sarà più preciso. Questo è il motivo per cui l'istruzione for è semplicemente un'espressione booleana: rende possibili cose come questa.

Answer 9

Si potrebbe voler esaminare Fermat's little theorem.

Ecco lo pseudo codice dal libro Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, dove n è il numero che si sta 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 di setacciatura. Tuttavia, ci sono numeri di Carmichael che superano il test di Fermat e NON sono primi. Ci sono soluzioni alternative per questo. Raccomando di consultare Section 1.3 in the fore mentioned book. Si tratta di test di primalità e potrebbe essere utile per te.

Answer 10

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

io non riesco a farlo più velocemente ...

Answer 11

Come disse Mark, il test di Miller-Rabin è in realtà un ottimo modo per andare. Un riferimento aggiuntivo (con pseudo-codice) è il Wikipedia article su di esso.

Si noti che mentre è probabilistico, testando solo un numero molto piccolo di casi, è possibile determinare se un numero è primo per i numeri nell'interv (e quasi lungo) intervallo. Vedere this part of that Wikipedia article o the Primality Proving reference per ulteriori dettagli.

Io consiglio anche la lettura this article su elevamento a potenza modulare, altrimenti si sta andando a che fare con molto molto grandi numeri quando si cerca di fare il test di Miller-Rabin ...

Answer 12

ho pensato Prime numbers and primality testing era utile ed i suoni AKS algoritmo interessante anche se non è particolarmente pratico se paragonato a un test basato probabilmente.

Answer 13

questo funziona molto veloce per i numeri primi test (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 

Answer 14

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, con l'eccezione di 2 e 3. Quindi, per prima cosa puoi verificare se l'input è divisibile per 2 o 3. Quindi, controlla tutti i numeri del modulo 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; 
      } 
     } 

Answer 15

Nel caso in cui qualcun altro sia interessato, ecco la mia conversione della procedura di Mohammad sopra a VBA. Ho aggiunto un controllo per escludere 1, 0 e numeri negativi poiché sono tutti definiti come non primi.

Ho testato solo questo 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