Quelle serait la méthode la plus rapide pour tester la primalité de Java?
j'essaie de trouver le moyen le plus rapide de vérifier si un nombre donné est Premier ou non (en Java). Ci-dessous sont plusieurs méthodes de test de primalité que j'ai inventé. Y a-t-il un meilleur moyen que la deuxième mise en œuvre(isPrime2)?
public class Prime {
public static boolean isPrime1(int n) {
if (n <= 1) {
return false;
}
if (n == 2) {
return true;
}
for (int i = 2; i <= Math.sqrt(n) + 1; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
public static boolean isPrime2(int n) {
if (n <= 1) {
return false;
}
if (n == 2) {
return true;
}
if (n % 2 == 0) {
return false;
}
for (int i = 3; i <= Math.sqrt(n) + 1; i = i + 2) {
if (n % i == 0) {
return false;
}
}
return true;
}
}
public class PrimeTest {
public PrimeTest() {
}
@Test
public void testIsPrime() throws IllegalArgumentException, IllegalAccessException, InvocationTargetException {
Prime prime = new Prime();
TreeMap<Long, String> methodMap = new TreeMap<Long, String>();
for (Method method : Prime.class.getDeclaredMethods()) {
long startTime = System.currentTimeMillis();
int primeCount = 0;
for (int i = 0; i < 1000000; i++) {
if ((Boolean) method.invoke(prime, i)) {
primeCount++;
}
}
long endTime = System.currentTimeMillis();
Assert.assertEquals(method.getName() + " failed ", 78498, primeCount);
methodMap.put(endTime - startTime, method.getName());
}
for (Entry<Long, String> entry : methodMap.entrySet()) {
System.out.println(entry.getValue() + " " + entry.getKey() + " Milli seconds ");
}
}
}
14 réponses
Voici une autre façon:
boolean isPrime(long n) {
if(n < 2) return false;
if(n == 2 || n == 3) return true;
if(n%2 == 0 || n%3 == 0) return false;
long sqrtN = (long)Math.sqrt(n)+1;
for(long i = 6L; i <= sqrtN; i += 6) {
if(n%(i-1) == 0 || n%(i+1) == 0) return false;
}
return true;
}
et BigInteger's isProbablePrime(...) est valide pour tous les 32 bits int.
EDIT
Notez que isProbablePrime(certainty) ne produisent pas toujours la bonne réponse. Lorsque la certitude est sur le bas côté, il produit des faux positifs, comme @dimo414 mentionné dans les commentaires.
malheureusement, je n'ai pas pu trouver la source qui revendiquait isProbablePrime(certainty) est valide pour tous (32 bits) int's (assez donné certitude!).
alors j'ai fait quelques tests. J'ai créé un BitSet taille Integer.MAX_VALUE/2 représentant tous les impairs et utilisé un premier tamis pour trouver tous les nombres premiers dans la gamme 1..Integer.MAX_VALUE. Je puis en boucle à partir de i=1..Integer.MAX_VALUE à vérifier que chaque new BigInteger(String.valueOf(i)).isProbablePrime(certainty) == isPrime(i).
pour la certitude 5 et 10,isProbablePrime(...) produit de faux positifs le long de la ligne. Mais avec isProbablePrime(15), aucun test n'a échoué.
Voici mon banc d'essai:
import java.math.BigInteger;
import java.util.BitSet;
public class Main {
static BitSet primes;
static boolean isPrime(int p) {
return p > 0 && (p == 2 || (p%2 != 0 && primes.get(p/2)));
}
static void generatePrimesUpTo(int n) {
primes = new BitSet(n/2);
for(int i = 0; i < primes.size(); i++) {
primes.set(i, true);
}
primes.set(0, false);
int stop = (int)Math.sqrt(n) + 1;
int percentageDone = 0, previousPercentageDone = 0;
System.out.println("generating primes...");
long start = System.currentTimeMillis();
for(int i = 0; i <= stop; i++) {
previousPercentageDone = percentageDone;
percentageDone = (int)((i + 1.0) / (stop / 100.0));
if(percentageDone <= 100 && percentageDone != previousPercentageDone) {
System.out.println(percentageDone + "%");
}
if(primes.get(i)) {
int number = (i * 2) + 1;
for(int p = number * 2; p < n; p += number) {
if(p < 0) break; // overflow
if(p%2 == 0) continue;
primes.set(p/2, false);
}
}
}
long elapsed = System.currentTimeMillis() - start;
System.out.println("finished generating primes ~" + (elapsed/1000) + " seconds");
}
private static void test(final int certainty, final int n) {
int percentageDone = 0, previousPercentageDone = 0;
long start = System.currentTimeMillis();
System.out.println("testing isProbablePrime(" + certainty + ") from 1 to " + n);
for(int i = 1; i < n; i++) {
previousPercentageDone = percentageDone;
percentageDone = (int)((i + 1.0) / (n / 100.0));
if(percentageDone <= 100 && percentageDone != previousPercentageDone) {
System.out.println(percentageDone + "%");
}
BigInteger bigInt = new BigInteger(String.valueOf(i));
boolean bigIntSays = bigInt.isProbablePrime(certainty);
if(isPrime(i) != bigIntSays) {
System.out.println("ERROR: isProbablePrime(" + certainty + ") returns "
+ bigIntSays + " for i=" + i + " while it " + (isPrime(i) ? "is" : "isn't" ) +
" a prime");
return;
}
}
long elapsed = System.currentTimeMillis() - start;
System.out.println("finished testing in ~" + ((elapsed/1000)/60) +
" minutes, no false positive or false negative found for isProbablePrime(" + certainty + ")");
}
public static void main(String[] args) {
int certainty = Integer.parseInt(args[0]);
int n = Integer.MAX_VALUE;
generatePrimesUpTo(n);
test(certainty, n);
}
}
lequel j'ai couru par faire:
java -Xmx1024m -cp . Main 15
la génération des amorces a pris environ 30 secondes sur ma machine. Et le test de tous les i1..Integer.MAX_VALUE a pris environ 2 heures et 15 minutes.
C'est la façon la plus élégante:
public static boolean isPrime(int n) {
return !new String(new char[n]).matches(".?|(..+?)\1+");
}
Java 1.4+. Aucune importation nécessaire.
Si court. Si belle.
vous avez franchi la première étape en éliminant tous les multiples de 2.
cependant, pourquoi vous êtes-vous arrêté là? vous auriez pu éliminer tous les multiples de 3 sauf 3, Tous les multiples de 5 sauf 5, etc.
quand vous suivez ce raisonnement jusqu'à sa conclusion, vous obtenez le tamis D'Eratosthènes.
Si vous essayez juste de trouver si un nombre est premier ou pas c'est assez bon, mais si vous essayez de trouver tous les nombres premiers de 0 à n une meilleure option sera le tamis D'Eratosthènes
mais cela dépendra des limitations de java sur les tailles de tableaux, etc.
votre algorithme fonctionnera bien pour des nombres relativement petits. Pour les grands nombres, des algorithmes avancés doivent être utilisés (basés par exemple sur des courbes elliptiques). Une autre idée sera d'utiliser un test "pseuso-primes". Ceux-ci vont tester rapidement qu'un nombre est un premier, mais ils ne sont pas 100% précis. Cependant, ils peuvent vous aider à quelques numéros plus vite que votre algorithme.
Enfin, bien que le compilateur va probablement optimiser pour vous, vous devriez écrire:
int max = (int) (Math.sqrt(n) + 1);
for (int i = 3; i <= max; i = i + 2) {
}
ce que vous avez écrit Est ce que font la plupart des programmeurs et qui devrait être suffisant la plupart du temps.
cependant, si vous êtes à la recherche du "meilleur algorithme scientifique", il existe de nombreuses variations (avec des niveaux de certitude variables) documentées http://en.wikipedia.org/wiki/Prime_number.
par exemple, si vous avez un nombre à 70 chiffres, les limitations physiques de JVM peuvent empêcher votre code de s'exécuter, auquel cas vous pouvez utiliser " tamis" etc.
encore une fois, comme je l'ai dit si c'était une question de programmation ou une question générale d'utilisation dans le logiciel votre code devrait être parfait :)
dépendant de la longueur du nombre que vous devez tester, vous pouvez précalculer une liste de nombres premiers pour les petites valeurs (n < 10^6), qui est utilisée en premier, si le nombre demandé est dans cette plage. C'est bien sûr le moyen le plus rapide. Comme mentionné dans d'autres réponses tamis D'Eratosthènes est la méthode préférée pour générer une telle précalculées liste.
si vos nombres sont plus grands que cela, vous pouvez utiliser le test de primalité de Rabin. primalité Rabin test
je pense que cette méthode est la meilleure. au moins pour moi-
public static boolean isPrime(int num)
{
for (int i = 2; i<= num/i; i++)
{
if (num % i == 0)
{
return false;
}
}
return num > 1;
}
un test rapide dû à Jaeschke (1993) est une version déterministe du test Miller-Rabin, qui n'a pas de faux positifs en dessous de 4 759 123 141 et peut donc être appliqué à Java ints.
// Given a positive number n, find the largest number m such
// that 2^m divides n.
private static int val2(int n) {
int m = 0;
if ((n&0xffff) == 0) {
n >>= 16;
m += 16;
}
if ((n&0xff) == 0) {
n >>= 8;
m += 8;
}
if ((n&0xf) == 0) {
n >>= 4;
m += 4;
}
if ((n&0x3) == 0) {
n >>= 2;
m += 2;
}
if (n > 1) {
m++
}
return m;
}
// For convenience, handle modular exponentiation via BigInteger.
private static int modPow(int base, int exponent, int m) {
BigInteger bigB = BigInteger.valueOf(base);
BigInteger bigE = BigInteger.valueOf(exponent);
BigInteger bigM = BigInteger.valueOf(m);
BigInteger bigR = bigB.modPow(bigE, bigM);
return bigR.intValue();
}
// Basic implementation.
private static boolean isStrongProbablePrime(int n, int base) {
int s = val2(n-1);
int d = modPow(b, n>>s, n);
if (d == 1) {
return true;
}
for (int i=1; i < s; i++) {
if (d+1 == n) {
return true;
}
d = d*d % n;
}
return d+1 == n;
}
public static boolean isPrime(int n) {
if ((n&1) == 0) {
return n == 2;
}
if (n < 9) {
return n > 1;
}
return isStrongProbablePrime(n, 2) && isStrongProbablePrime(n, 7) && isStrongProbablePrime(n, 61);
}
Cela ne fonctionne pas
ces deux tests sont beaucoup plus rapides que n'importe quel type de division de première instance.
il y a bien sûr des centaines de tests de primalité, tous avec divers avantages et désavantages basés sur la taille du nombre, des formes spéciales, la taille du facteur, etc.
Cependant, en java je trouve que le plus utile est celui-ci:
BigInteger.valueOf(long/int num).isProbablePrime(int certainty);
il est déjà mis en œuvre, et il est assez rapide (je trouve qu'il faut ~6 secondes pour une matrice 1000x1000 remplie de longs 0-2^64 et une certitude de 15) et probablement mieux optimisé que tout ce que nous les mortels pourrait venir avec.
Il utilise une version de l' test de primalité Baillie–PSW, qui n'a pas de savoir contre-exemples. (bien qu'il puisse utiliser une version légèrement plus faible du test, qui peut parfois errer. peut-être)
j'ai optimisé la division de première instance ici: elle retourne un Booléen. Les méthodes autres que isPrime(n) sont également nécessaires.
static boolean[] smlprime = {false, false, true, true, false, true, false, true, false, false, false, true, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, true, false, false, false, true, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, true, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false, false, true, false, false};
public static boolean isPrime(long n) { //optimised
if (n < 2) {
return false;
}
if (n < smlprime.length) //less than smlprime.length do not need to be checked
{
return smlprime[(int) n]; //lol already checked
}
long[] dgt = longDigits(n);
long ones = dgt[dgt.length - 1];
if (ones % 2 == 0) {
return false;
}
if (ones == 0 || ones == 5) {
return false;
}
if (digitadd(n) % 3 == 0) {
return false;
}
if (n % 7 == 0) {
return false;
}
if (Square(n)) {
return false;
}
long hf = (long) Math.sqrt(n);
for (long j = 11; j < hf; j = nextProbablePrime(j)) {
//System.out.prlongln(Math.sqrt(i));
if (n % j == 0) {
return false;
}
//System.out.prlongln("res"+res);
}
return true;
}
public static long nextProbablePrime(long n) {
for (long i = n;; i++) {
if (i % 2 != 0 && i % 3 != 0 && i % 7 != 0) {
return i;
}
}
}
public static boolean Square(long n) {
long root = (long) Math.sqrt(n);
return root * root == n;
}
public static long[] longDigits(long n) {
String[] a = Long.toString(n).split("(?!^)");
long[] out = new long[a.length];
for (int i = 0; i < a.length; i++) {
out[i] = Long.parseLong(a[i]);
}
return out;
}
public static long digitadd(long n) {
long[] dgts = longDigits(n);
long ans = 0;
for (long i : dgts) {
ans += i;
}
return ans;
}
Note: Cet exemple de code ci-dessous contient des variables de comptage et des appels à une fonction d'impression pour les besoins de l'impression des résultats:
import java.util.*;
class Primality{
private static void printStats(int count, int n, boolean isPrime) {
System.err.println( "Performed " + count + " checks, determined " + n
+ ( (isPrime) ? " is PRIME." : " is NOT PRIME." ) );
}
/**
* Improved O( n^(1/2)) ) Algorithm
* Checks if n is divisible by 2 or any odd number from 3 to sqrt(n).
* The only way to improve on this is to check if n is divisible by
* all KNOWN PRIMES from 2 to sqrt(n).
*
* @param n An integer to be checked for primality.
* @return true if n is prime, false if n is not prime.
**/
public static boolean primeBest(int n){
int count = 0;
// check lower boundaries on primality
if( n == 2 ){
printStats(++count, n, true);
return true;
} // 1 is not prime, even numbers > 2 are not prime
else if( n == 1 || (n & 1) == 0){
printStats(++count, n, false);
return false;
}
double sqrtN = Math.sqrt(n);
// Check for primality using odd numbers from 3 to sqrt(n)
for(int i = 3; i <= sqrtN; i += 2){
count++;
// n is not prime if it is evenly divisible by some 'i' in this range
if( n % i == 0 ){
printStats(++count, n, false);
return false;
}
}
// n is prime
printStats(++count, n, true);
return true;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
while(scan.hasNext()) {
int n = scan.nextInt();
primeBest(n);
System.out.println();
}
scan.close();
}
}
quand le nombre premier 2147483647 est entré, il produit la sortie suivante:
a effectué 23170 contrôles, déterminé que 2147483647 est PREMIER.
testé dans un atome Intel @ 1.60 GHz, 2 Go RAM, système d'exploitation 32 bits
résultat du test:
le plus grand nombre premier en dessous de Long.MAX_VALUE=9223372036854775807 is 9223372036854775783
le temps écoulé est de 171499 millisecondes ou 2 minutes et 51 secondes
public class PrimalityTest
{
public static void main(String[] args)
{
long current_local_time = System.currentTimeMillis();
long long_number = 9223372036854775783L;
long long_a;
long long_b;
if (long_number < 2)
{
System.out.println(long_number + " is not a prime number");
}
else if (long_number < 4)
{
System.out.println(long_number + " is a prime number");
}
else if (long_number % 2 == 0)
{
System.out.println(long_number + " is not a prime number and is divisible by 2");
}
else
{
long_a = (long) (Math.ceil(Math.sqrt(long_number)));
terminate_loop:
{
for (long_b = 3; long_b <= long_a; long_b += 2)
{
if (long_number % long_b == 0)
{
System.out.println(long_number + " is not a prime number and is divisible by " + long_b);
break terminate_loop;
}
}
System.out.println(long_number + " is a prime number");
}
}
System.out.println("elapsed time: " + (System.currentTimeMillis() - current_local_time) + " millisecond/s");
}
}