Comment puis-je test de primalité?

Malheureusement, je n'ai pas essayé les approches algorithmiques avant. Mais si vous voulez mettre en oeuvre votre approche efficace, je vous suggère de faire quelques mise en cache. Créer un tableau pour stocker tous les nombres premiers inférieurs à un seuil défini, remplir ce tableau, et de chercher à l'intérieur/à l'aide d'.

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, qui est 821,461 pour un 64 ko de mémoire tampon), et est optimisé pour les autres cas (en cochant mod plus de 64 ko de numéros de la première de 820 000 -- 8% environ).

(Note: Ne pas prendre cette réponse comme "optimal". C'est plus d'un exemple sur la manière d'optimiser votre mise en œuvre.)

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

OriginalL'auteur Hosam Aly

Je ne sais pas si c'est tout à fait ce que vous cherchez, mais si vous êtes vraiment préoccupé par la vitesse, alors vous devriez regarder dans probabiliste des méthodes de test de primalité plutôt qu'à l'aide d'un tamis. Rabin-Miller est un test de primalité probabiliste utilisé par Mathematica.

OriginalL'auteur Mark Lavin

Comme dit Mark, de Miller-Rabin test est effectivement une très bonne façon d'aller. Une référence supplémentaire (pseudo-code) est le Article de Wikipedia à ce sujet.

Il convient de noter que, même si elle est probabiliste, en testant seulement un très petit nombre de cas, vous pouvez déterminer si un nombre est premier pour les nombres dans l'int (et près de long). Voir cette partie de l'article de Wikipédia, ou la Primalité de Prouver référence pour plus de détails.

Je vous recommande également la lecture de cet article sur l'exponentiation modulaire, car sinon, vous allez être face à de très grands nombres lorsque l'on essaie de Miller-Rabin test...

OriginalL'auteur Ant

...

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 a utilisé ce à quelques reprises.. Pas aussi rapidement comme un tamis.. mais ça marche.

OriginalL'auteur Inisheer

J'ai un algorithme rapide pour le contrôle de nombres premiers. Vous pouvez améliorer votre algorithme si vous savez que les nombres premiers sont de la forme 6k ± 1, à l'exception de 2 et 3. Alors, tout d'abord, vous pouvez vérifier si l'entrée est divisible par 2 ou 3. Ensuite, vérifier tous les nombres de la forme 6k ± 1 ≤ √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;
}
}

OriginalL'auteur Vahid

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 n'arrive pas à faire plus vite...

OriginalL'auteur Milan

Cela fonctionne très rapide 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

OriginalL'auteur Charles Okwuagwu

Votre pour la boucle devrait ressembler à ceci:

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

De cette façon, vous évitez le calcul en virgule flottante. Doit courir plus vite et ce sera plus précis. C'est pourquoi le for instruction conditionnelle est tout simplement une expression booléenne: il fait des choses comme cela possible.

OriginalL'auteur Samir Talwar