Vérifier si un entier est premier plus efficacement

Votre premier chèque est très inefficace. En fait, vous n'avez pas besoin de re-vérifier les multiples de déjà vérifié les numéros. Ainsi, lorsque vous vérifiez %2, vous n'avez pas besoin de vérifier pour %4.

Pour savoir si un nombre est un nombre premier, vous n'avez qu'à essayer de le diviser par tous les nombres premiers connus jusqu'à atteindre la racine carrée du nombre à être vérifié. En faisant cela réduit le nombre de divisions largement: si votre application dispose d'une liste des nombres premiers de 2..~44721 (par exemple calculé comme étape de préparation), vous pouvez vérifier tous les nombres jusqu'à 2000000000 assez rapidement.

Aussi, assurez-vous de vérifier le plus petit des deux permutations première (par exemple, dans l'échantillon de la première case 13, 31).

Edit:

Voici un exemple, j'ai rapidement mis en C# (vous aurez besoin de faire quelques petits changements syntaxiques de le faire tourner sur Java, mais j'ai juste eu un compilateur C# à la main):

public static long reverse(long value) {
long result = 0;
while (value > 0) {
result = result*10+(value%10);
value /= 10;
}
return result;
}
public static long[] knownPrimes = new long[1000000];
public static int knownPrimeCount = 0;
public static bool isPrime(long value) {
//we loop through all already known primes and try to divide by those (sieve sort of)
for (int primeIndex = 0; primeIndex < knownPrimeCount; primeIndex++) {
long primeToCheck = knownPrimes[primeIndex];
if (value % knownPrimes[primeIndex] == 0) {
//can be divided by the given prime -> not a prime
return false;
}
if ((primeToCheck * primeToCheck) > value) {
//square exceeds the value -> is a prime, no more checks needed
return true;
}
}
//if we come here, we've run out of primes to check against, and therefore we should indicate this as error
throw new ArgumentException(string.Format("{0} is too large to be checked against known primes", value), "value");
}
public static void Main(String[] args){
long loop = 2000000000;
long n =    1999990000;
//first we initialize all the primes we may be needing for the final computation
knownPrimes[knownPrimeCount++] = 2;
for (long i = 3; true; i++) {
if (isPrime(i)) {
//store the new prime
knownPrimes[knownPrimeCount++] = i;
if ((i * i) > loop) {
break; //we have all the primes we need now
}
}
}
//now we try to find matches
for (long i = n; i <= loop; i++) {
long reversed = reverse(i);
if ((reversed <= i) && isPrime(reversed) && isPrime(i)) {
Console.WriteLine("{0} <-> {1}", i, reversed);
}
}
Console.WriteLine("#");
Console.ReadKey(true);
}

Sur mon ordinateur et avec le loop et n dans la source, le résultat s'affiche instantanément.

OriginalL'auteur Lucero

Il semble que vous êtes en augmentant de 1, mais vous devriez être en augmentant de 2. Pas de même le nombre est premier, mais 2.

OriginalL'auteur Mantas Vidutis

Je n'ai pas fait cela avant, mais voici quelques choses qui viennent à mon esprit.

si votre racine carrée est un entier, le nombre n'est pas premier

si le nombre se termine par un 0,2,4,5,6, ou 8 il n'est pas premier, à l'exception des 2 lui-même

Nombre est divisible par 3 si la somme ofdigits est divisible par 3
et par 9 si la somme est 9.

Je ne sais pas si les tests pour ce genre de choses vous aider, au moins le test de la racine carrée devrait aider parce que vous avez à calculer de toute façon et vous avez peut-être déjà fait.

Oh, et bien sûr votre efficence augmente beaucoup si vous faites quelque chose comme de Miller–Rabin test de primalité http://en.wikipedia.org/wiki/Miller-Rabin_primality_test.
Votre test ne doit être effectué dans les cas qui ne coûtent pas certain.

OriginalL'auteur HansDampf

@outis...je vois ce que vous dites c'est un petit truc utile que je dois dire. je vous remercie pour cela.

@Graham...aussi cool j'ai lu un article sur le test que vous avez mentionné parce que même si je crois que j'ai compris l'essentiel à partir des commentaires que vous faites Python a toujours l'air comme le grec pour moi. Je sais tout le monde dit que c'est l'un des plus simple des langues à ramasser, mais pour quelque raison que ce soit java et c++ toujours regarder plus lisible pour moi. De toute façon, oui, qui wouldve été une bien meilleure façon de le faire. Merci encore à vous tous, qui m'a donné des conseils, j'ai appris beaucoup de cette commission. Peut pas pour mes structures de données et algorithmes de la classe à l'automne!!!

OriginalL'auteur SipSop

@David obtenir la racine carrée d'un nombre, puis en boucle jusqu'à la racine carrée d'éliminer les même nombres et de voir si il n'est pas divisble

OriginalL'auteur Dead Programmer