Comment puis-je tester la primalité?
https://stackoverflow.com/questions/627463
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'écris une petite bibliothèque avec des méthodes liées aux nombres premiers. Après avoir jeté les bases (méthodes de travail) et maintenant je cherche une optimisation. Bien sûr, Internet est un excellent endroit pour le faire. Cependant, je suis tombé sur un problème d'arrondi et je me demandais comment résoudre ce problème.
Dans la boucle que j’utilise pour tester la primalité d’un nombre, il est plus efficace de rechercher jusqu’à sqrt (n) au lieu de n / 2 ou même de n - 1. Mais, en raison de problèmes d’arrondi, certains nombres sont ignorés et certains nombres premiers sont donc ignorés. sauté! Par exemple, le 10000ème nombre premier devrait être: 104729, mais la version "optimisée" se termine par: 103811.
Certains codes (ils sont ouverts à plus d'optimisation, je sais, mais je ne peux gérer qu'une chose à la fois):
/// <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;
}
Je sais que la partie carrée me manque (ou que je échoue), a également essayé Math.Ceiling, avec à peu près les mêmes résultats.
La solution
Malheureusement, je n’ai jamais essayé les approches algorithmiques auparavant. Mais si vous souhaitez implémenter votre approche efficacement, je vous suggérerais de mettre en cache. Créez un tableau pour stocker tous les nombres premiers inférieurs à un seuil défini, remplissez ce tableau et effectuez une recherche dans / l’utiliser.
Dans l'exemple suivant, déterminer si un nombre est premier est O (1) dans le meilleur des cas (à savoir, lorsque le nombre est inférieur ou égal à maxPrime , soit 821 461 pour un 64 Ko). (tampon), et est quelque peu optimisé pour les autres cas (en vérifiant le mod sur seulement 64 000 nombres sur les 820 000 premiers - environ 8%).
(Remarque: ne considérez pas cette réponse comme une approche "optimale". Il s'agit davantage d'un exemple d'optimisation de votre implémentation.)
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;
}
}
Autres conseils
Je suppose que c'est votre problème:
for (int idx = 3; idx < flooredAndSquared; idx++)
Cela devrait être
for (int idx = 3; idx <= flooredAndSquared; idx++)
afin que vous n'obteniez pas de nombres carrés comme nombres premiers. De même, vous pouvez utiliser & id; idx + = 2 " au lieu de " idx ++ " car vous devez uniquement tester les nombres impairs (comme vous l'avez écrit dans le commentaire ci-dessus ...).
Je ne sais pas si c'est tout à fait ce que vous recherchez, mais si vous êtes vraiment préoccupé par la rapidité, vous devriez vous pencher sur des méthodes probabilistes pour tester la primalité plutôt que d'utiliser un tamis. Rabin-Miller est un test de primalité probabiliste utilisé par Mathematica.
J'ai posté une classe qui utilise le tamis ou Eratosthenes pour calculer les nombres premiers ici:
La taille d'un tableau est-elle limitée par la limite supérieure de int (2147483647)?
Comme Mark l'a dit, le test Miller-Rabin est en fait un très bon moyen d'aller de l'avant. Une référence supplémentaire (avec pseudo-code) est le article de Wikipedia à propos de il.
Il convient de noter que, même s’il est probabiliste, il n’est possible de déterminer si un nombre est primordial que pour les nombres compris entre int (et presque long) en ne testant qu’un très petit nombre de cas. Voir cette partie de cet article de Wikipedia ou la référence Primality Proving pour plus de détails.
Je vous recommanderais également de lire cet article sur l'exonération modulaire, sinon vous y allez être confronté à de très grands nombres en essayant de faire le test Miller-Rabin ...
Vous voudrez peut-être examiner le le petit théorème de Fermat .
Voici le pseudo-code du livre Algorithmes de S. Dasgupta, C.H. Papadimitriou et UV Vazirani , où n est le nombre que vous testez pour 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
La mise en œuvre du théorème de Fermat devrait être plus rapide que la solution de tamisage. Cependant, il y a des nombres de Carmichael qui passent le test de Fermat et ne sont PAS premiers. Il existe des solutions de contournement pour cela. Je recommande de consulter la section 1.3 du livre susmentionné . Tout est une question de test de primalité et pourrait vous être utile.
Essayez ceci ...
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;
Je l'ai déjà utilisé plusieurs fois .. Pas aussi vite qu'un tamis .. mais ça marche.
Voici une fonction à moitié décente que j'ai écrite pour résoudre l'un des problèmes d'Euler:
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;
}
}
J'ai un algorithme rapide pour vérifier les nombres premiers. Vous pouvez améliorer votre algorithme si vous savez que les nombres premiers sont sous la forme 6k & # 177; 1, à l'exception de 2 et 3. Donc, vous pouvez d'abord vérifier si l'entrée est divisible par 2 ou 3. Ensuite, vérifiez tous les numéros du formulaire 6k & # 177; 1 & # 8804; & # 8730; entrée.
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;
}
}
Essayez le le tamis d'eratosthenes - qui devrait vous empêcher d'obtenir la racine et le point flottant problèmes.
Comme pour le étage , vous serez mieux servi en prenant le plafond .
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;
}
Je ne peux pas l'obtenir plus vite ...
Je pensais Test des nombres premiers et des primalités était utile et l’algorithme AKS semble intéressant même s’il n’est pas particulièrement pratique comparé aux tests probabily.
Cela fonctionne très vite pour tester les nombres premiers (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
Au cas où quelqu'un d'autre serait intéressé, voici ma conversion de la procédure de Mohammad ci-dessus en VBA. J'ai ajouté un chèque pour exclure les nombres 1, 0 et négatifs, car ils sont tous définis comme non premiers.
J'ai seulement testé cela dans 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
Votre boucle for devrait ressembler à ceci:
for (int idx = 3; idx * idx <= test; idx++) { ... }
Ainsi, vous évitez les calculs en virgule flottante. Devrait courir plus vite et ce sera plus précis. C’est la raison pour laquelle l’instruction for conditionnelle est simplement une expression booléenne: elle rend les choses comme celles-ci possibles.
