Explication du générateur de nombres premiers?

Je cherchais un algorithme pour générer des nombres premiers. J'ai trouvé le suivant réalisé par Robert William Hanks. C'est très efficace et meilleur que les autres algorithmes mais je ne peux pas comprendre les maths derrière ça.Explication du générateur de nombres premiers?

def primes(n): 
    """ Returns a list of primes < n """ 
    lis = [True] * n 
    for i in range(3,int(n**0.5)+1,2): 
     if lis[i]: 
      lis[i*i::2*i]=[False]*int((n-i*i-1)/(2*i)+1) 
    return [2] + [i for i in range(3,n,2) if lis[i]]

Quelle est la relation entre l'ensemble des valeurs de True et le tableau premier numéros final?

Source

2017-03-15 majid5_

On dirait qu'il utilise le tamis d'Ératosthène. – ForceBru

Ce code de [cette réponse] (http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188) est fondamentalement légèrement optimisé Tamis d'Ératosthène. Notez que c'est du code Python 2, il faut quelques tweaks à utiliser sur Python 3. FWIW, j'ai une version Python 3 du code de RWH dans [cette réponse] (http://stackoverflow.com/a/38743446/4014959) . –

Parcourez-le avec 'n = 6', notez (sur papier) la valeur de' lis' et 'i' lorsque vous parcourez la boucle. –

partir de nTrue valeurs, avec i dénombrés à partir de -sqrt(n) par l'étape de , si i entrée e est encore True, note toutes les entrées de i^2 à l'extrémité de la matrice par l'étape de 2*i comme False (ce seront les multiples de i).

Toutes les entrées True impaires qui sont laissées dans le tableau sont des nombres premiers.

Source

2017-03-15 13:57:33

Explication du générateur de nombres premiers?

Répondre

Questions connexes