Existe-t-il un algorithme simple permettant de déterminer si X est premier ?

Question

J'ai essayé de travailler sur le projet Euler, et j'ai remarqué qu'une poignée de problèmes vous demandent de déterminer un nombre premier.

1. Je sais que je peux simplement diviser x par 2, 3, 4, 5, ..., racine carrée de X et si j'arrive à la racine carrée, je peux (sans risque) supposer que le nombre est premier. Malheureusement, cette solution semble assez compliquée.

2. J'ai cherché de meilleurs algorithmes pour déterminer si un nombre est premier, mais je m'embrouille vite.

Existe-t-il un algorithme simple qui puisse déterminer si X est premier, sans embrouiller un simple programmeur mortel ?

Merci beaucoup !

Answer 1

Le premier algorithme est assez bon et est très utilisé dans le projet Euler. Si vous connaissez le nombre maximum que vous voulez, vous pouvez également rechercher le tamis d'Eratosthène.

Si vous conservez la liste des nombres premiers, vous pouvez également affiner le premier algorithme pour ne diviser qu'avec des nombres premiers jusqu'à la racine carrée du nombre.

Avec ces deux algorithmes (la division et le tamis), vous devriez être en mesure de résoudre les problèmes.

Modifier : correction du nom comme indiqué dans les commentaires

Answer 2

Pour générer tous les nombres premiers inférieurs à une limite Le tamis d'Eratosthène (la page contient des variantes dans 20 langages de programmation) est la solution la plus ancienne et la plus simple.

En Python :

def iprimes_upto(limit):
    is_prime = [True] * limit
    for n in range(2, limit):
        if is_prime[n]:
           yield n
           for i in range(n*n, limit, n): # start at ``n`` squared
               is_prime[i] = False

Ejemplo:

>>> list(iprimes_upto(15))
[2, 3, 5, 7, 11, 13]

Answer 3

Je vois que le test de primalité de Fermat a déjà été suggéré, mais j'ai travaillé à travers Structure et interprétation des programmes informatiques et ils donnent également le Test de Miller-Rabin (voir section 1.2.6, problème 1.28) comme autre alternative. Je l'ai utilisé avec succès pour les problèmes d'Euler.

Answer 4

En gardant à l'esprit les faits suivants (tirés de MathsChallenge.net ):

• Tous les nombres premiers sauf 2 sont impairs.
• Tous les nombres premiers supérieurs à 3 peuvent être écrits sous la forme 6k - 1 ou 6k + 1.
• Vous n'avez pas besoin de vérifier au-delà de la racine carrée de n

Voici la fonction C++ que j'utilise pour des n relativement petits :

bool isPrime(unsigned long n)
{
    if (n == 1) return false; // 1 is not prime
    if (n < 4) return true; // 2 and 3 are both prime
    if ((n % 2) == 0) return false; // exclude even numbers
    if (n < 9) return true; //we have already excluded 4, 6, and 8.
    if ((n % 3) == 0) return false; // exclude remaining multiples of 3

    unsigned long r = floor( sqrt(n) );
    unsigned long f = 5;
    while (f <= r)
    {
        if ((n % f) == 0)  return false;
        if ((n % (f + 2)) == 0) return false;
        f = f + 6;
    }
    return true; // (in all other cases)
}

Vous pourriez probablement trouver d'autres optimisations.

Answer 5

Voici une optimisation simple de votre méthode qui n'est pas tout à fait le tamis d'Eratosthène mais qui est très facile à mettre en œuvre : essayez d'abord de diviser X par 2 et 3, puis bouclez sur j=1..sqrt(X)/6, en essayant de diviser par 6*j-1 et 6*j+1. Cette méthode ignore automatiquement tous les nombres divisibles par 2 ou 3, ce qui vous permet d'obtenir une accélération à facteur constant plutôt agréable.