La manière la plus rapide de lister tous les nombres premiers en dessous de N

question connexe (traitant des générateurs de primes et incluant les benchmarks):

accélérer les opérations bitstring/bit en Python?

pour un python 3 versions utilisant bytearray & compress voir: https://stackoverflow.com/a/46635266/350331

plus rapide et plus de mémoire-Sage Python code pur:

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

ou à partir d'un demi-tamis

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

plus Rapide et plus de mémoire-sage numpy code:

import numpy
def primesfrom3to(n):
    """ Returns a array of primes, 3 <= p < n """
    sieve = numpy.ones(n/2, dtype=numpy.bool)
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i/2]:
            sieve[i*i/2::i] = False
    return 2*numpy.nonzero(sieve)[0][1::]+1

une variation plus rapide à partir d'un tiers de tamis:

import numpy
def primesfrom2to(n):
    """ Input n>=6, Returns a array of primes, 2 <= p < n """
    sieve = numpy.ones(n/3 + (n%6==2), dtype=numpy.bool)
    for i in xrange(1,int(n**0.5)/3+1):
        if sieve[i]:
            k=3*i+1|1
            sieve[       k*k/3     ::2*k] = False
            sieve[k*(k-2*(i&1)+4)/3::2*k] = False
    return numpy.r_[2,3,((3*numpy.nonzero(sieve)[0][1:]+1)|1)]

(dur-à-code) pur python version du code ci-dessus serait:

def primes2(n):
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    n, correction = n-n%6+6, 2-(n%6>1)
    sieve = [True] * (n/3)
    for i in xrange(1,int(n**0.5)/3+1):
      if sieve[i]:
        k=3*i+1|1
        sieve[      k*k/3      ::2*k] = [False] * ((n/6-k*k/6-1)/k+1)
        sieve[k*(k-2*(i&1)+4)/3::2*k] = [False] * ((n/6-k*(k-2*(i&1)+4)/6-1)/k+1)
    return [2,3] + [3*i+1|1 for i in xrange(1,n/3-correction) if sieve[i]]

malheureusement pur-python n'adopte pas la manière plus simple et plus rapide de faire des assignations, et appeler len() à l'intérieur de la boucle comme dans [False]*len(sieve[((k*k)/3)::2*k]) est trop lent. Donc j'ai dû improviser pour corriger la saisie (et éviter plus de mathématiques) et faire des mathématiques extrêmes (et douloureuses)-magie.

Personnellement, je pense que c'est une honte que numpy (qui est si largement utilisé) ne fait pas partie de la bibliothèque standard de python(2 ans après la sortie de python 3 et pas de compatibilité avec numpy), et que les améliorations de la syntaxe et de la vitesse semblent complètement ignorées par les développeurs python.

il y a un bel échantillon du Livre De Cuisine En Python ici -- la version la plus rapide proposée sur cette URL est:

import itertools
def erat2( ):
    D = {  }
    yield 2
    for q in itertools.islice(itertools.count(3), 0, None, 2):
        p = D.pop(q, None)
        if p is None:
            D[q*q] = q
            yield q
        else:
            x = p + q
            while x in D or not (x&1):
                x += p
            D[x] = p

pour que ça donne

def get_primes_erat(n):
  return list(itertools.takewhile(lambda p: p<n, erat2()))

mesurant à l'invite de la coque (comme je préfère le faire) avec ce code en pri.py, j'observe:

$ python2.5 -mtimeit -s'import pri' 'pri.get_primes(1000000)'
10 loops, best of 3: 1.69 sec per loop
$ python2.5 -mtimeit -s'import pri' 'pri.get_primes_erat(1000000)'
10 loops, best of 3: 673 msec per loop

il semble donc que la solution de Livre de cuisine est plus de deux fois plus rapide.

en utilisant le tamis de Sundaram , je pense que j'ai battu le record de pure-Python:

def sundaram3(max_n):
    numbers = range(3, max_n+1, 2)
    half = (max_n)//2
    initial = 4

    for step in xrange(3, max_n+1, 2):
        for i in xrange(initial, half, step):
            numbers[i-1] = 0
        initial += 2*(step+1)

        if initial > half:
            return [2] + filter(None, numbers)

comparaison:

C:\USERS>python -m timeit -n10 -s "import get_primes" "get_primes.get_primes_erat(1000000)"
10 loops, best of 3: 710 msec per loop

C:\USERS>python -m timeit -n10 -s "import get_primes" "get_primes.daniel_sieve_2(1000000)"
10 loops, best of 3: 435 msec per loop

C:\USERS>python -m timeit -n10 -s "import get_primes" "get_primes.sundaram3(1000000)"
10 loops, best of 3: 327 msec per loop

l'algorithme est rapide, mais il a un défaut grave:

>>> sorted(get_primes(530))
[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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163,
167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251,
257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443,
449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 527, 529]
>>> 17*31
527
>>> 23*23
529

Vous supposez que numbers.pop() renvoie le plus petit nombre dans l'ensemble, mais ce n'est pas garanti à tous. Les ensembles ne sont pas ordonnés et pop() supprime et renvoie un élément arbitraire , de sorte qu'il ne peut pas être utilisé pour sélectionner le premier suivant parmi les nombres restants.

pour truly la solution la plus rapide avec un N suffisamment grand serait de télécharger une liste pré-calculée de nombres premiers , de la stocker comme un tuple et de faire quelque chose comme:

for pos,i in enumerate(primes):
    if i > N:
        print primes[:pos]

Si N > primes[-1] seulement , puis de calculer les nombres premiers et enregistrer la nouvelle liste dans votre code, donc la prochaine fois, il est tout aussi rapide.

toujours sortir des sentiers battus.

si vous ne voulez pas réinventer la roue, vous pouvez installer la bibliothèque de mathématiques symboliques sympy (Oui c'est compatible Python 3)

pip install sympy

et utiliser la primerange fonction

from sympy import sieve
primes = list(sieve.primerange(1, 10**6))

il est instructif d'écrire votre propre code de recherche prime, mais il est également utile d'avoir une bibliothèque fiable rapide à portée de main. J'ai écrit un wrapper autour de la bibliothèque C++ primesieve , l'a appelé primesieve-python

Essayer pip install primesieve

import primesieve
primes = primesieve.generate_primes(10**8)

je serais curieux de voir la vitesse comparée.

si vous acceptez itertools mais pas numpy, voici une adaptation de rwh_primes2 pour Python 3 qui tourne environ deux fois plus vite sur ma machine. Le seul changement important est d'utiliser un bytearray au lieu d'une liste pour le booléen, et d'utiliser compress au lieu d'une compréhension de liste pour construire la liste finale. (J'aimerais ajouter un commentaire comme moarningsun si j'étais capable.)

import itertools
izip = itertools.zip_longest
chain = itertools.chain.from_iterable
compress = itertools.compress
def rwh_primes2_python3(n):
    """ Input n>=6, Returns a list of primes, 2 <= p < n """
    zero = bytearray([False])
    size = n//3 + (n % 6 == 2)
    sieve = bytearray([True]) * size
    sieve[0] = False
    for i in range(int(n**0.5)//3+1):
      if sieve[i]:
        k=3*i+1|1
        start = (k*k+4*k-2*k*(i&1))//3
        sieve[(k*k)//3::2*k]=zero*((size - (k*k)//3 - 1) // (2 * k) + 1)
        sieve[  start ::2*k]=zero*((size -   start  - 1) // (2 * k) + 1)
    ans = [2,3]
    poss = chain(izip(*[range(i, n, 6) for i in (1,5)]))
    ans.extend(compress(poss, sieve))
    return ans

Comparaisons:

>>> timeit.timeit('primes.rwh_primes2(10**6)', setup='import primes', number=1)
0.0652179726976101
>>> timeit.timeit('primes.rwh_primes2_python3(10**6)', setup='import primes', number=1)
0.03267321276325674

et

>>> timeit.timeit('primes.rwh_primes2(10**8)', setup='import primes', number=1)
6.394284538007014
>>> timeit.timeit('primes.rwh_primes2_python3(10**8)', setup='import primes', number=1)
3.833829450302801

déterministe de la mise en œuvre de Miller-Rabin test de Primalité sur l'hypothèse que N < 9,080,191

import sys
import random

def miller_rabin_pass(a, n):
    d = n - 1
    s = 0
    while d % 2 == 0:
        d >>= 1
        s += 1

    a_to_power = pow(a, d, n)
    if a_to_power == 1:
        return True
    for i in xrange(s-1):
        if a_to_power == n - 1:
            return True
        a_to_power = (a_to_power * a_to_power) % n
    return a_to_power == n - 1


def miller_rabin(n):
    for a in [2, 3, 37, 73]:
      if not miller_rabin_pass(a, n):
        return False
    return True


n = int(sys.argv[1])
primes = [2]
for p in range(3,n,2):
  if miller_rabin(p):
    primes.append(p)
print len(primes)

selon L'article sur Wikipedia ( http://en.wikipedia.org/wiki/Miller-Rabin_primality_test ) test n < 9.080.191 pour a = 2,3,37, et 73 est suffisant pour décider si N est composite ou non.

et j'ai adapté le code source de la mise en œuvre probabiliste de L'original Miller-Rabin test trouvé ici: http://en.literateprograms.org/Miller-Rabin_primality_test_ (Python)

si vous avez le contrôle sur N, le moyen le plus rapide de lister tous les nombres premiers est de les précalculer. Sérieusement. Précomputer est une optimisation négligée.

voici le code que j'utilise normalement pour générer des nombres premiers en Python:

$ python -mtimeit -s'import sieve' 'sieve.sieve(1000000)' 
10 loops, best of 3: 445 msec per loop
$ cat sieve.py
from math import sqrt

def sieve(size):
 prime=[True]*size
 rng=xrange
 limit=int(sqrt(size))

 for i in rng(3,limit+1,+2):
  if prime[i]:
   prime[i*i::+i]=[False]*len(prime[i*i::+i])

 return [2]+[i for i in rng(3,size,+2) if prime[i]]

if __name__=='__main__':
 print sieve(100)

il ne peut pas rivaliser avec les solutions plus rapides affichés ici, mais au moins il est python pur.

Merci d'avoir posté cette question. J'ai vraiment appris beaucoup de choses aujourd'hui.

pour le code le plus rapide, la solution de numpy est la meilleure. Pour des raisons purement académiques, cependant, je poste ma version de python pur, qui est un peu moins de 50% plus rapide que la version de Livre de cuisine posté ci-dessus. Puisque je fais la liste entière dans la mémoire, vous avez besoin de suffisamment d'espace pour tenir tout, mais il semble assez bien échelle.

def daniel_sieve_2(maxNumber):
    """
    Given a number, returns all numbers less than or equal to
    that number which are prime.
    """
    allNumbers = range(3, maxNumber+1, 2)
    for mIndex, number in enumerate(xrange(3, maxNumber+1, 2)):
        if allNumbers[mIndex] == 0:
            continue
        # now set all multiples to 0
        for index in xrange(mIndex+number, (maxNumber-3)/2+1, number):
            allNumbers[index] = 0
    return [2] + filter(lambda n: n!=0, allNumbers)

et les résultats:

>>>mine = timeit.Timer("daniel_sieve_2(1000000)",
...                    "from sieves import daniel_sieve_2")
>>>prev = timeit.Timer("get_primes_erat(1000000)",
...                    "from sieves import get_primes_erat")
>>>print "Mine: {0:0.4f} ms".format(min(mine.repeat(3, 1))*1000)
Mine: 428.9446 ms
>>>print "Previous Best {0:0.4f} ms".format(min(prev.repeat(3, 1))*1000)
Previous Best 621.3581 ms

Un peu différente de la mise en œuvre d'une demi-tamis à l'aide de Numpy:

http://rebrained.com/?p=458

import math
import numpy
def prime6(upto):
    primes=numpy.arange(3,upto+1,2)
    isprime=numpy.ones((upto-1)/2,dtype=bool)
    for factor in primes[:int(math.sqrt(upto))]:
        if isprime[(factor-2)/2]: isprime[(factor*3-2)/2:(upto-1)/2:factor]=0
    return numpy.insert(primes[isprime],0,2)

Quelqu'un peut-il comparer cela avec les autres horaires? Sur ma machine, il semble assez comparable à l'autre demi-tamis.

tout est écrit et testé. Donc, il n'est pas nécessaire de réinventer la roue.

python -m timeit -r10 -s"from sympy import sieve" "primes = list(sieve.primerange(1, 10**6))"

nous donne un record de rupture 12.2 msec !

10 loops, best of 10: 12.2 msec per loop

si ce n'est pas assez rapide, vous pouvez essayer PyPy:

pypy -m timeit -r10 -s"from sympy import sieve" "primes = list(sieve.primerange(1, 10**6))"

qui se traduit par:

10 loops, best of 10: 2.03 msec per loop

la réponse avec 247 up-votes listes 15.9 ms pour la meilleure solution. Comparer cette!!!

voici deux versions mises à jour (pure Python 3.6) de l'une des fonctions les plus rapides,

from itertools import compress

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

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

première utilisation de python, donc certaines des méthodes que j'utilise dans ce cas peuvent sembler un peu encombrantes. Je viens tout juste de convertir mon code c++ en python et c'est ce que j'ai (bien qu'un peu lent en python)

#!/usr/bin/env python
import time

def GetPrimes(n):

    Sieve = [1 for x in xrange(n)]

    Done = False
    w = 3

    while not Done:

        for q in xrange (3, n, 2):
            Prod = w*q
            if Prod < n:
                Sieve[Prod] = 0
            else:
                break

        if w > (n/2):
            Done = True
        w += 2

    return Sieve



start = time.clock()

d = 10000000
Primes = GetPrimes(d)

count = 1 #This is for 2

for x in xrange (3, d, 2):
    if Primes[x]:
        count+=1

elapsed = (time.clock() - start)
print "\nFound", count, "primes in", elapsed, "seconds!\n"

pythonw Primes.py

a trouvé 664579 nombres premiers en 12.799119 secondes!

#!/usr/bin/env python
import time

def GetPrimes2(n):

    Sieve = [1 for x in xrange(n)]

    for q in xrange (3, n, 2):
        k = q
        for y in xrange(k*3, n, k*2):
            Sieve[y] = 0

    return Sieve



start = time.clock()

d = 10000000
Primes = GetPrimes2(d)

count = 1 #This is for 2

for x in xrange (3, d, 2):
    if Primes[x]:
        count+=1

elapsed = (time.clock() - start)
print "\nFound", count, "primes in", elapsed, "seconds!\n"

pythonw Primes2.py

Found 664579 amorces dans 10.230172 secondes!

#!/usr/bin/env python
import time

def GetPrimes3(n):

    Sieve = [1 for x in xrange(n)]

    for q in xrange (3, n, 2):
        k = q
        for y in xrange(k*k, n, k << 1):
            Sieve[y] = 0

    return Sieve



start = time.clock()

d = 10000000
Primes = GetPrimes3(d)

count = 1 #This is for 2

for x in xrange (3, d, 2):
    if Primes[x]:
        count+=1

elapsed = (time.clock() - start)
print "\nFound", count, "primes in", elapsed, "seconds!\n"

python Primes2.py

a trouvé 664579 nombres premiers en 7.113776 secondes!

je sais que le concours est fermé depuis quelques années. ...

néanmoins c'est ma suggestion pour un tamis Python pur premier, basé sur l'omission des multiples de 2, 3 et 5 en utilisant les étapes appropriées pendant le traitement du tamis en avant. Néanmoins, il est en fait plus lent pour N<10 ^ 9 que @Robert William Hanks superior solutions rwh_primes2 et rwh_primes1. En utilisant des ctypes.c_ushort sieve array au-dessus de 1.5* 10^8 Il est en quelque sorte adaptable aux limites de la mémoire.

10^6

$ python-mtimeit-s"import primeSieveSpeedComp" "primeSieveSpeedComp.primeSieveSeq (1000000)" 10 boucles, le meilleur de 3: 46.7 msec par boucle

à comparer:$ python -mtimeit-s " import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes1(1000000)" 10 boucles, best of 3: 43.2 msec par boucle comparer: $ python-m timeit-s " importer primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes2(1000000)" 10 boucles, le meilleur des 3: 34.5 msec par boucle

10^7

$ python-mtimeit-s"import primeSieveSpeedComp" "primeSieveSpeedComp.primeSieveSeq (10000000)" 10 boucles, le meilleur de 3: 530 msec par boucle

à comparer:$ python -mtimeit-s " import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes1(10000000)" 10 boucles, best of 3: 494 msec par boucle comparer: $ python-m timeit-s " importer primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes2(10000000)" 10 boucles, best of 3: 375 msec par boucle

10^8

$ python-mtimeit-s"import primeSieveSpeedComp" "primeSieveSpeedComp.primeSieveSeq (100000000)" 10 boucles, le meilleur de 3: 5.55 sec par boucle

à comparer: $ python -mtimeit-s " import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes1(100000000)" 10 boucles, best of 3: 5.33 sec par boucle de comparer: $ python-m timeit-s " importer primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes2(100000000)" 10 boucles, best of 3: 3.95 sec par boucle

10^9

$ python-mtimeit-s"import primeSieveSpeedComp" "primeSieveSpeedComp.primeSieveSeq (1000000000)" 10 boucles, le meilleur de 3: 61.2 sec par boucle

à comparer: $ python -mtimeit-n 3-s " import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes1 (1000000000) "3 loops, best of 3: 97.8 sec par boucle

à comparer: $ python-m timeit-s " import primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes2(1000000000)" 10 boucles, le meilleur des 3: 41,9 sec par boucle 151920920"

vous pouvez copier le code ci-dessous dans ubuntus primeSieveSpeedComp pour revoir ces tests.

def primeSieveSeq(MAX_Int):
    if MAX_Int > 5*10**8:
        import ctypes
        int16Array = ctypes.c_ushort * (MAX_Int >> 1)
        sieve = int16Array()
        #print 'uses ctypes "unsigned short int Array"'
    else:
        sieve = (MAX_Int >> 1) * [False]
        #print 'uses python list() of long long int'
    if MAX_Int < 10**8:
        sieve[4::3] = [True]*((MAX_Int - 8)/6+1)
        sieve[12::5] = [True]*((MAX_Int - 24)/10+1)
    r = [2, 3, 5]
    n = 0
    for i in xrange(int(MAX_Int**0.5)/30+1):
        n += 3
        if not sieve[n]:
            n2 = (n << 1) + 1
            r.append(n2)
            n2q = (n2**2) >> 1
            sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
        n += 2
        if not sieve[n]:
            n2 = (n << 1) + 1
            r.append(n2)
            n2q = (n2**2) >> 1
            sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
        n += 1
        if not sieve[n]:
            n2 = (n << 1) + 1
            r.append(n2)
            n2q = (n2**2) >> 1
            sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
        n += 2
        if not sieve[n]:
            n2 = (n << 1) + 1
            r.append(n2)
            n2q = (n2**2) >> 1
            sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
        n += 1
        if not sieve[n]:
            n2 = (n << 1) + 1
            r.append(n2)
            n2q = (n2**2) >> 1
            sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
        n += 2
        if not sieve[n]:
            n2 = (n << 1) + 1
            r.append(n2)
            n2q = (n2**2) >> 1
            sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
        n += 3
        if not sieve[n]:
            n2 = (n << 1) + 1
            r.append(n2)
            n2q = (n2**2) >> 1
            sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
        n += 1
        if not sieve[n]:
            n2 = (n << 1) + 1
            r.append(n2)
            n2q = (n2**2) >> 1
            sieve[n2q::n2] = [True]*(((MAX_Int >> 1) - n2q - 1) / n2 + 1)
    if MAX_Int < 10**8:
        return [2, 3, 5]+[(p << 1) + 1 for p in [n for n in xrange(3, MAX_Int >> 1) if not sieve[n]]]
    n = n >> 1
    try:
        for i in xrange((MAX_Int-2*n)/30 + 1):
            n += 3
            if not sieve[n]:
                r.append((n << 1) + 1)
            n += 2
            if not sieve[n]:
                r.append((n << 1) + 1)
            n += 1
            if not sieve[n]:
                r.append((n << 1) + 1)
            n += 2
            if not sieve[n]:
                r.append((n << 1) + 1)
            n += 1
            if not sieve[n]:
                r.append((n << 1) + 1)
            n += 2
            if not sieve[n]:
                r.append((n << 1) + 1)
            n += 3
            if not sieve[n]:
                r.append((n << 1) + 1)
            n += 1
            if not sieve[n]:
                r.append((n << 1) + 1)
    except:
        pass
    return r

j'ai testé quelques fonctions d'unutbu , Je l'ai calculé avec le nombre de millions affamés

les gagnants sont les fonctions qui utilisent la bibliothèque de numpy,

Note : Il serait également intéressant de faire une utilisation de la mémoire du test :)

code échantillon

code complet sur mon dépôt github

#!/usr/bin/env python

import lib
import timeit
import sys
import math
import datetime

import prettyplotlib as ppl
import numpy as np

import matplotlib.pyplot as plt
from prettyplotlib import brewer2mpl

primenumbers_gen = [
    'sieveOfEratosthenes',
    'ambi_sieve',
    'ambi_sieve_plain',
    'sundaram3',
    'sieve_wheel_30',
    'primesfrom3to',
    'primesfrom2to',
    'rwh_primes',
    'rwh_primes1',
    'rwh_primes2',
]

def human_format(num):
    # /q/formatting-long-numbers-as-strings-in-python-60557/"Compute prime number to %(n)s" % locals())
    print("")

    results = dict()
    for pgen in primenumbers_gen:
        results[pgen] = dict()
        benchtimes = list()
        for n in nbs:
            t = timeit.Timer("lib.%(pgen)s(n)" % locals(), setup=config)
            execute_times = t.repeat(repeat=nb_benchloop,number=1)
            benchtime = np.mean(execute_times)
            benchtimes.append(benchtime)
        results[pgen] = {'benchtimes':np.array(benchtimes)}

fig, ax = plt.subplots(1)
plt.ylabel('Computation time (in second)')
plt.xlabel('Numbers computed')
i = 0
for pgen in primenumbers_gen:

    bench = results[pgen]['benchtimes']
    avgs = np.divide(bench,nbs)
    avg = np.average(bench, weights=nbs)

    # Compute linear regression
    A = np.vstack([nbs, np.ones(len(nbs))]).T
    a, b = np.linalg.lstsq(A, nbs*avgs)[0]

    # Plot
    i += 1
    #label="%(pgen)s" % locals()
    #ppl.plot(nbs, nbs*avgs, label=label, lw=1, linestyle='--', color=set2[i % 12])
    label="%(pgen)s avg" % locals()
    ppl.plot(nbs, a * nbs + b, label=label, lw=2, color=set2[i % 12])
print datetime.datetime.now().strftime(datetimeformat)

ppl.legend(ax, loc='upper left', ncol=4)

# Change x axis label
ax.get_xaxis().get_major_formatter().set_scientific(False)
fig.canvas.draw()
labels = [human_format(int(item.get_text())) for item in ax.get_xticklabels()]

ax.set_xticklabels(labels)
ax = plt.gca()

plt.show()

Pour Python 3

def rwh_primes2(n):
    correction = (n%6>1)
    n = {0:n,1:n-1,2:n+4,3:n+3,4:n+2,5:n+1}[n%6]
    sieve = [True] * (n//3)
    sieve[0] = False
    for i in range(int(n**0.5)//3+1):
      if sieve[i]:
        k=3*i+1|1
        sieve[      ((k*k)//3)      ::2*k]=[False]*((n//6-(k*k)//6-1)//k+1)
        sieve[(k*k+4*k-2*k*(i&1))//3::2*k]=[False]*((n//6-(k*k+4*k-2*k*(i&1))//6-1)//k+1)
    return [2,3] + [3*i+1|1 for i in range(1,n//3-correction) if sieve[i]]

à mon avis, le le plus rapide de toutes les façons est de coder les nombres premiers de votre code.

alors pourquoi ne pas simplement écrire un script lent qui génère un autre fichier source qui contient tous les numéros, puis importer ce fichier source lorsque vous exécutez votre programme.

bien sûr, cela ne fonctionne que si vous connaissez la limite supérieure de N au moment de la compilation, mais c'est le cas pour (presque) tous les problèmes du projet Euler.

PS: "je pourrais me tromper bien que IFF Parser la source avec des nombres premiers câblés soit plus lent que de les calculer en premier lieu, mais pour autant que je sache Python fonctionne à partir des fichiers compilés .pyc donc lire un tableau binaire avec tous les nombres premiers jusqu'à N devrait être très rapide dans ce cas.

désolé de vous déranger mais erat2 () a un défaut sérieux dans l'algorithme.

lors de la recherche du prochain composite, nous avons besoin de tester des nombres impairs seulement. q,p les deux sont impairs; alors q+p est même et n'a pas besoin d'être testé, mais q+2*p est toujours impair. Cela élimine le test" if even " dans la condition de boucle while et économise environ 30% du temps d'exécution.

tant que nous y sommes: au lieu de l'élégant "D. pop (Q, aucun)' get and delete method use ' if q in D: p = D[q],del D [q]' Qui est deux fois plus rapide! Au moins sur ma machine (P3-1GHz). Je suggère donc cette implémentation de cet algorithme astucieux:

def erat3( ):
    from itertools import islice, count

    # q is the running integer that's checked for primeness.
    # yield 2 and no other even number thereafter
    yield 2
    D = {}
    # no need to mark D[4] as we will test odd numbers only
    for q in islice(count(3),0,None,2):
        if q in D:                  #  is composite
            p = D[q]
            del D[q]
            # q is composite. p=D[q] is the first prime that
            # divides it. Since we've reached q, we no longer
            # need it in the map, but we'll mark the next
            # multiple of its witnesses to prepare for larger
            # numbers.
            x = q + p+p        # next odd(!) multiple
            while x in D:      # skip composites
                x += p+p
            D[x] = p
        else:                  # is prime
            # q is a new prime.
            # Yield it and mark its first multiple that isn't
            # already marked in previous iterations.
            D[q*q] = q
            yield q

la méthode la plus rapide que j'ai essayée jusqu'à présent est basée sur le Python cookbook erat2 fonction:

import itertools as it
def erat2a( ):
    D = {  }
    yield 2
    for q in it.islice(it.count(3), 0, None, 2):
        p = D.pop(q, None)
        if p is None:
            D[q*q] = q
            yield q
        else:
            x = q + 2*p
            while x in D:
                x += 2*p
            D[x] = p

Voir ce répondre pour une explication de l'accélération.

je peux être en retard à la fête, mais je vais devoir ajouter mon propre code pour cela. Il utilise environ n / 2 dans l'espace parce que nous n'avons pas besoin de stocker des nombres pairs et je fais également usage du module Python bitarray, réduisant encore drastiquement la consommation de mémoire et permettant de calculer tous les nombres premiers jusqu'à 1.000.000.000

from bitarray import bitarray
def primes_to(n):
    size = n//2
    sieve = bitarray(size)
    sieve.setall(1)
    limit = int(n**0.5)
    for i in range(1,limit):
        if sieve[i]:
            val = 2*i+1
            sieve[(i+i*val)::val] = 0
    return [2] + [2*i+1 for i, v in enumerate(sieve) if v and i > 0]

python -m timeit -n10 -s "import euler" "euler.primes_to(1000000000)"
10 loops, best of 3: 46.5 sec per loop

il a été exécuté sur un MAC OSX 64bit 2,4 GHZ 10.8.3

j'ai collectionné plusieurs tamis de nombres premiers au fil du temps. Le plus rapide sur mon ordinateur est celui-ci:

from time import time
# 175 ms for all the primes up to the value 10**6
def primes_sieve(limit):
    a = [True] * limit
    a[0] = a[1] = False
    #a[2] = True
    for n in xrange(4, limit, 2):
        a[n] = False
    root_limit = int(limit**.5)+1
    for i in xrange(3,root_limit):
        if a[i]:
            for n in xrange(i*i, limit, 2*i):
                a[n] = False
    return a

LIMIT = 10**6
s=time()
primes = primes_sieve(LIMIT)
print time()-s

je suis lent à répondre à cette question, mais il a semblé comme un exercice amusant. J'utilise num PY ce qui pourrait être de la triche et je doute que cette méthode soit la plus rapide mais elle devrait être claire. Il tamise un tableau booléen se référant à ses seuls indices et provoque des nombres premiers à partir des indices de toutes les valeurs vraies. Pas besoin de modulo.

import numpy as np
def ajs_primes3a(upto):
    mat = np.ones((upto), dtype=bool)
    mat[0] = False
    mat[1] = False
    mat[4::2] = False
    for idx in range(3, int(upto ** 0.5)+1, 2):
        mat[idx*2::idx] = False
    return np.where(mat == True)[0]

Voici une technique intéressante pour générer des nombres premiers (mais pas la plus efficace) en utilisant les compréhensions de la liste de python:

noprimes = [j for i in range(2, 8) for j in range(i*2, 50, i)]
primes = [x for x in range(2, 50) if x not in noprimes]

vous pouvez trouver l'exemple et quelques explications à droite ici

en général, si vous avez besoin de calcul rapide des nombres, python n'est pas le meilleur choix. Aujourd'hui, il ya beaucoup d'algorithme plus rapide (et complexe). Par exemple, sur mon ordinateur j'ai eu 2,2 secondes pour votre code, avec Mathematica j'ai eu 0,088005.

tout d'abord: Avez-vous besoin de set?

c'est une solution élégante et simple pour trouver des nombres premiers en utilisant une liste stockée. Commence par un 4 variables, vous n'avez qu'à tester des nombres premiers impairs pour les diviseurs, et vous n'avez qu'à tester jusqu'à la moitié du nombre que vous testez comme un premier (aucun point dans le test si 9, 11, 13 diviser en 17). Il teste des nombres premiers précédemment stockés comme diviseurs.

    # Program to calculate Primes
 primes = [1,3,5,7]
for n in range(9,100000,2):
    for x in range(1,(len(primes)/2)):
        if n % primes[x] == 0:
            break
    else:
        primes.append(n)
print primes

c'est la façon dont vous pouvez comparer avec d'autres.

# You have to list primes upto n
nums = xrange(2, n)
for i in range(2, 10):
    nums = filter(lambda s: s==i or s%i, nums)
print nums

si simple...