algoritmo migliore e più usato per trovare la primalità di un dato numero positivo [chiuso]

Per il primo test di numeri molto grandi, ci sono metodi probabilistici:

link

Most popular primality tests are probabilistic tests. These tests use, apart from the tested number n, some other numbers a which are chosen at random from some sample space; the usual randomized primality tests never report a prime number as composite, but it is possible for a composite number to be reported as prime. The probability of error can be reduced by repeating the test with several independently chosen values of a...

Il modo più veloce sarà una tabella di ricerca :

This page indexes many of the lists of primes stored at this site. The main list we keep is the list of the 5000 largest known primes and selected smaller primes. We also have list of the first primes, but it is not practical to keep too long of such list...

Un metodo molto veloce di Rifiutare un primato di prova consiste nell'utilizzare il fatto che tutti i numeri primi sono nella forma 6k +/- 1, dove k è un numero intero positivo. (2 e 3 escluso).

Questo significa che puoi rifiutare un numero con solo due test (più il banale).

public static boolean checkPrime(long p)
{
   if (p==2 || p==3) return true;
   if ( (p+1) % 6 == 0 || (p-1) % 6 == 0 ) 
   {
      // p might be prime, worth checking
      return checkProbablePrime(p);
   }
   else
   {
     // p is not prime.
     return false;  
   }
} 

Indipendentemente dal fatto che questa sia una buona tecnica dipende dalla distribuzione degli input. Se ti aspetti un'alta percentuale di numeri composti, allora questo è un modo rapido per eliminarli dalla contesa. Sarebbe bello eliminare il ramo triviale in alto (== 2, == 3) ma ciò dipende dal contesto degli input. Se il tuo obiettivo è quello di trovare i primi, allora dovresti saltare questo.