Pour la définition de ce qu'est un nombre premier, voir ici: http://fr.wikipedia.org/wiki/Nombre_premier
Les fonctions présentées ici renverront la liste des nombres premiers. Par exemple:
premiers(100) => [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
Le principe du calcul est indiqué ici: http://fr.wikipedia.org/wiki/Crible_d'%C3%89ratosth%C3%A8ne
A part la version récursive, que je n'utilise pas à cause des limites de Python (pile<1000), la version la plus efficace et la plus élégante que j'ai trouvée sur le web est la suivante:
def premiers(n): """""" L = range(0,n+1) L[1] = 0 k = 2 while k*k <= n: L[k*2::k] = [0]*len(L[k*2::k]) k += 1 return [x for x in L if x]
Cette version est de plus très rapide. Par exemple, avec l'accélérateur psyco, on trouve les 664579 nombres premiers inférieurs à 10 millions en une dizaine de secondes!!!
Malheureusement, cette méthode a une limite: malgré une mémoire “confortable” (2Go), mon Python refuse d'exécuter avec n > 10 millions environ.
Le principe du calcul est assez simple. Pour le nombre n donné, on teste chacun des nombres de 2 à n pour savoir s'il est premier. Pour chaque test, le nombre est premier si on ne lui a pas trouvé de diviseur. Quand le nombre est premier, on le conserve dans une liste. A la fin, on renvoie cette liste.
Pour gagner du temps, on utilise plusieurs astuces:
- A part “2” qui est premier, on ne teste pas les nombres pairs qui ne sont forcément pas premiers.
- Pour chaque nombre k à tester, On arrête les divisions à racine de k parce que si on n'a pas encore trouvé de diviseur, on n'en trouvera plus après, et le nombre est donc premier.
- Comme on doit conserver tous les nombres premiers trouvés, on n'utilise qu'eux comme diviseur dans les tests de division!
Pour vérifier, vous pouvez voir ici pas mal de nombres premiers déjà calculés: http://nombrespremiersliste.free.fr/
Voilà le code proposé:
def premiers(n, p=[2,3,5]): """Retourne la liste des nombres premiers <= n (méthode=division)""" k = p[-1]+2 if n < k: return [x for x in p if x<=n] while k <= n: i = 0 while i < len(p): if p[i]*p[i] > k: p.append(k) break if (k % p[i]) == 0: break i += 1 k += 2 return p # Exemple d'utilisation print premiers(100) # affiche [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
Performance: Cette fonction est très rapide. Par exemple, toujours avec l'accélérateur psyco, la fonction trouve les 5.761.455 nombres premiers inférieurs à 100 millions en une centaine de secondes. A noter que l'affichage de cette très longue liste sera plus longue que son calcul…
Avec cette fonction, on peut avoir n=1 milliard, et on trouve alors les 50.847.534 nombres premiers en à peu près 40 minutes. Mais il ne faut pas rêver: le temps de calcul grimpe très très vite, et ce n'est pas avec ça que vous allez casser le cryptage RSA: le dernier cryptage factorisé, le RSA-640, a demandé plus de 5 mois de calcul avec 30 CPU … Et on en est maintenant au RSA-2048 qui correspond à un nombre d'environ 600 chiffres!
Cas particulier: si n=1, la fonction renvoie une liste vide, parce que “1” n'est pas un nombre premier.
Vous pouvez bien entendu ajouter un test pour empêcher que la fonction ne soit appelée avec n<=0.
Vous pouvez tester cette fonction avec la Calculext ici: http://calculext.jpvweb.com, mais soyez raisonnable: au delà de premiers(100000), vous allez dépasser le temps maxi (8s) de calcul autorisé sur le serveur (qui, de plus, n'a pas psyco).