N aşağıdaki tüm asal listelemek için en hızlı yolu

bu benim gelebileceğim en iyi algoritma.

def get_primes(n):
    numbers = set(range(n, 1, -1))
    primes = []
    while numbers:
        p = numbers.pop()
        primes.append(p)
        numbers.difference_update(set(range(p*2, n+1, p)))
    return primes

>>> timeit.Timer(stmt='get_primes.get_primes(1000000)', setup='import   get_primes').timeit(1)
1.1499958793645562

daha hızlı yapılabilir mi?

bu kodun bir kusuru vardır: numbers sıralanmamış bir set olduğundan, numbers.pop() setten en düşük sayıyı kaldıracağının garantisi yoktur. Bununla birlikte, bazı giriş numaraları için (en azından benim için) çalışır:

>>> sum(get_primes(2000000))
142913828922L
#That's the correct sum of all numbers below 2 million
>>> 529 in get_primes(1000)
False
>>> 529 in get_primes(530)
True
317
tarihinde sordu bjb568 2010-01-15 02:40:27
kaynak

30 ответов

Uyarı: timeit sonuçları nedeniyle donanım veya Python sürümü.

aşağıda uygulamaları bir dizi karşılaştırır bir komut dosyası:

' 'sieve_wheel_30' i dikkatime getirmek için çok teşekkürler. Kredi gider Robert William Hanks için primesfrom2to, primesfrom3to, rwh_primes, rwh_primes1, ve rwh_primes2.

Test edilen düz Python yöntemlerinin

, psyco ile , n=1000000 için, rwh_primes1 oldu en hızlı test edildi.

+---------------------+-------+
| Method              | ms    |
+---------------------+-------+
| rwh_primes1         | 43.0  |
| sieveOfAtkin        | 46.4  |
| rwh_primes          | 57.4  |
| sieve_wheel_30      | 63.0  |
| rwh_primes2         | 67.8  |    
| sieveOfEratosthenes | 147.0 |
| ambi_sieve_plain    | 152.0 |
| sundaram3           | 194.0 |
+---------------------+-------+
Test edilen düz Python yöntemlerinin

, psyco olmadan , n=1000000 için, rwh_primes2 en hızlıydı.

+---------------------+-------+
| Method              | ms    |
+---------------------+-------+
| rwh_primes2         | 68.1  |
| rwh_primes1         | 93.7  |
| rwh_primes          | 94.6  |
| sieve_wheel_30      | 97.4  |
| sieveOfEratosthenes | 178.0 |
| ambi_sieve_plain    | 286.0 |
| sieveOfAtkin        | 314.0 |
| sundaram3           | 416.0 |
+---------------------+-------+
Test edilen tüm yöntemlerin , , numpy , n=1000000 için, primesfrom2to en hızlı test edildi.

+---------------------+-------+
| Method              | ms    |
+---------------------+-------+
| primesfrom2to       | 15.9  |
| primesfrom3to       | 18.4  |
| ambi_sieve          | 29.3  |
+---------------------+-------+

zamanlamaları komutu kullanılarak ölçüldü:

python -mtimeit -s"import primes" "primes.{method}(1000000)"

ile {method} yöntem adlarının her biri ile değiştirilir.

primes.py:

#!/usr/bin/env python
import psyco; psyco.full()
from math import sqrt, ceil
import numpy as np

def rwh_primes(n):
    # /q/fastest-way-to-list-all-primes-below-n-35838/""" 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]]

def rwh_primes1(n):
    # /q/fastest-way-to-list-all-primes-below-n-35838/""" 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]]

def rwh_primes2(n):
    # /q/fastest-way-to-list-all-primes-below-n-35838/""" Input n>=6, Returns a list of primes, 2 <= p < 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 xrange(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 xrange(1,n/3-correction) if sieve[i]]

def sieve_wheel_30(N):
    # http://zerovolt.com/?p=88
    ''' Returns a list of primes <= N using wheel criterion 2*3*5 = 30

Copyright 2009 by zerovolt.com
This code is free for non-commercial purposes, in which case you can just leave this comment as a credit for my work.
If you need this code for commercial purposes, please contact me by sending an email to: info [at] zerovolt [dot] com.'''
    __smallp = ( 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, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599,
    601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683,
    691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797,
    809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887,
    907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997)

    wheel = (2, 3, 5)
    const = 30
    if N < 2:
        return []
    if N <= const:
        pos = 0
        while __smallp[pos] <= N:
            pos += 1
        return list(__smallp[:pos])
    # make the offsets list
    offsets = (7, 11, 13, 17, 19, 23, 29, 1)
    # prepare the list
    p = [2, 3, 5]
    dim = 2 + N // const
    tk1  = [True] * dim
    tk7  = [True] * dim
    tk11 = [True] * dim
    tk13 = [True] * dim
    tk17 = [True] * dim
    tk19 = [True] * dim
    tk23 = [True] * dim
    tk29 = [True] * dim
    tk1[0] = False
    # help dictionary d
    # d[a , b] = c  ==> if I want to find the smallest useful multiple of (30*pos)+a
    # on tkc, then I need the index given by the product of [(30*pos)+a][(30*pos)+b]
    # in general. If b < a, I need [(30*pos)+a][(30*(pos+1))+b]
    d = {}
    for x in offsets:
        for y in offsets:
            res = (x*y) % const
            if res in offsets:
                d[(x, res)] = y
    # another help dictionary: gives tkx calling tmptk[x]
    tmptk = {1:tk1, 7:tk7, 11:tk11, 13:tk13, 17:tk17, 19:tk19, 23:tk23, 29:tk29}
    pos, prime, lastadded, stop = 0, 0, 0, int(ceil(sqrt(N)))
    # inner functions definition
    def del_mult(tk, start, step):
        for k in xrange(start, len(tk), step):
            tk[k] = False
    # end of inner functions definition
    cpos = const * pos
    while prime < stop:
        # 30k + 7
        if tk7[pos]:
            prime = cpos + 7
            p.append(prime)
            lastadded = 7
            for off in offsets:
                tmp = d[(7, off)]
                start = (pos + prime) if off == 7 else (prime * (const * (pos + 1 if tmp < 7 else 0) + tmp) )//const
                del_mult(tmptk[off], start, prime)
        # 30k + 11
        if tk11[pos]:
            prime = cpos + 11
            p.append(prime)
            lastadded = 11
            for off in offsets:
                tmp = d[(11, off)]
                start = (pos + prime) if off == 11 else (prime * (const * (pos + 1 if tmp < 11 else 0) + tmp) )//const
                del_mult(tmptk[off], start, prime)
        # 30k + 13
        if tk13[pos]:
            prime = cpos + 13
            p.append(prime)
            lastadded = 13
            for off in offsets:
                tmp = d[(13, off)]
                start = (pos + prime) if off == 13 else (prime * (const * (pos + 1 if tmp < 13 else 0) + tmp) )//const
                del_mult(tmptk[off], start, prime)
        # 30k + 17
        if tk17[pos]:
            prime = cpos + 17
            p.append(prime)
            lastadded = 17
            for off in offsets:
                tmp = d[(17, off)]
                start = (pos + prime) if off == 17 else (prime * (const * (pos + 1 if tmp < 17 else 0) + tmp) )//const
                del_mult(tmptk[off], start, prime)
        # 30k + 19
        if tk19[pos]:
            prime = cpos + 19
            p.append(prime)
            lastadded = 19
            for off in offsets:
                tmp = d[(19, off)]
                start = (pos + prime) if off == 19 else (prime * (const * (pos + 1 if tmp < 19 else 0) + tmp) )//const
                del_mult(tmptk[off], start, prime)
        # 30k + 23
        if tk23[pos]:
            prime = cpos + 23
            p.append(prime)
            lastadded = 23
            for off in offsets:
                tmp = d[(23, off)]
                start = (pos + prime) if off == 23 else (prime * (const * (pos + 1 if tmp < 23 else 0) + tmp) )//const
                del_mult(tmptk[off], start, prime)
        # 30k + 29
        if tk29[pos]:
            prime = cpos + 29
            p.append(prime)
            lastadded = 29
            for off in offsets:
                tmp = d[(29, off)]
                start = (pos + prime) if off == 29 else (prime * (const * (pos + 1 if tmp < 29 else 0) + tmp) )//const
                del_mult(tmptk[off], start, prime)
        # now we go back to top tk1, so we need to increase pos by 1
        pos += 1
        cpos = const * pos
        # 30k + 1
        if tk1[pos]:
            prime = cpos + 1
            p.append(prime)
            lastadded = 1
            for off in offsets:
                tmp = d[(1, off)]
                start = (pos + prime) if off == 1 else (prime * (const * pos + tmp) )//const
                del_mult(tmptk[off], start, prime)
    # time to add remaining primes
    # if lastadded == 1, remove last element and start adding them from tk1
    # this way we don't need an "if" within the last while
    if lastadded == 1:
        p.pop()
    # now complete for every other possible prime
    while pos < len(tk1):
        cpos = const * pos
        if tk1[pos]: p.append(cpos + 1)
        if tk7[pos]: p.append(cpos + 7)
        if tk11[pos]: p.append(cpos + 11)
        if tk13[pos]: p.append(cpos + 13)
        if tk17[pos]: p.append(cpos + 17)
        if tk19[pos]: p.append(cpos + 19)
        if tk23[pos]: p.append(cpos + 23)
        if tk29[pos]: p.append(cpos + 29)
        pos += 1
    # remove exceeding if present
    pos = len(p) - 1
    while p[pos] > N:
        pos -= 1
    if pos < len(p) - 1:
        del p[pos+1:]
    # return p list
    return p

def sieveOfEratosthenes(n):
    """sieveOfEratosthenes(n): return the list of the primes < n."""
    # Code from: <[email protected]>, Nov 30 2006
    # http://groups.google.com/group/comp.lang.python/msg/f1f10ced88c68c2d
    if n <= 2:
        return []
    sieve = range(3, n, 2)
    top = len(sieve)
    for si in sieve:
        if si:
            bottom = (si*si - 3) // 2
            if bottom >= top:
                break
            sieve[bottom::si] = [0] * -((bottom - top) // si)
    return [2] + [el for el in sieve if el]

def sieveOfAtkin(end):
    """sieveOfAtkin(end): return a list of all the prime numbers <end
    using the Sieve of Atkin."""
    # Code by Steve Krenzel, <[email protected]>, improved
    # Code: https://web.archive.org/web/20080324064651/http://krenzel.info/?p=83
    # Info: http://en.wikipedia.org/wiki/Sieve_of_Atkin
    assert end > 0
    lng = ((end-1) // 2)
    sieve = [False] * (lng + 1)

    x_max, x2, xd = int(sqrt((end-1)/4.0)), 0, 4
    for xd in xrange(4, 8*x_max + 2, 8):
        x2 += xd
        y_max = int(sqrt(end-x2))
        n, n_diff = x2 + y_max*y_max, (y_max << 1) - 1
        if not (n & 1):
            n -= n_diff
            n_diff -= 2
        for d in xrange((n_diff - 1) << 1, -1, -8):
            m = n % 12
            if m == 1 or m == 5:
                m = n >> 1
                sieve[m] = not sieve[m]
            n -= d

    x_max, x2, xd = int(sqrt((end-1) / 3.0)), 0, 3
    for xd in xrange(3, 6 * x_max + 2, 6):
        x2 += xd
        y_max = int(sqrt(end-x2))
        n, n_diff = x2 + y_max*y_max, (y_max << 1) - 1
        if not(n & 1):
            n -= n_diff
            n_diff -= 2
        for d in xrange((n_diff - 1) << 1, -1, -8):
            if n % 12 == 7:
                m = n >> 1
                sieve[m] = not sieve[m]
            n -= d

    x_max, y_min, x2, xd = int((2 + sqrt(4-8*(1-end)))/4), -1, 0, 3
    for x in xrange(1, x_max + 1):
        x2 += xd
        xd += 6
        if x2 >= end: y_min = (((int(ceil(sqrt(x2 - end))) - 1) << 1) - 2) << 1
        n, n_diff = ((x*x + x) << 1) - 1, (((x-1) << 1) - 2) << 1
        for d in xrange(n_diff, y_min, -8):
            if n % 12 == 11:
                m = n >> 1
                sieve[m] = not sieve[m]
            n += d

    primes = [2, 3]
    if end <= 3:
        return primes[:max(0,end-2)]

    for n in xrange(5 >> 1, (int(sqrt(end))+1) >> 1):
        if sieve[n]:
            primes.append((n << 1) + 1)
            aux = (n << 1) + 1
            aux *= aux
            for k in xrange(aux, end, 2 * aux):
                sieve[k >> 1] = False

    s  = int(sqrt(end)) + 1
    if s  % 2 == 0:
        s += 1
    primes.extend([i for i in xrange(s, end, 2) if sieve[i >> 1]])

    return primes

def ambi_sieve_plain(n):
    s = range(3, n, 2)
    for m in xrange(3, int(n**0.5)+1, 2): 
        if s[(m-3)/2]: 
            for t in xrange((m*m-3)/2,(n>>1)-1,m):
                s[t]=0
    return [2]+[t for t in s if t>0]

def sundaram3(max_n):
    # /q/fastest-way-to-list-all-primes-below-n-35838/""" Returns a array of primes, p < n """
    assert n>=2
    sieve = np.ones(n/2, dtype=np.bool)
    for i in xrange(3,int(n**0.5)+1,2):
        if sieve[i/2]:
            sieve[i*i/2::i] = False
    return np.r_[2, 2*np.nonzero(sieve)[0][1::]+1]    

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

if __name__=='__main__':
    import itertools
    import sys

    def test(f1,f2,num):
        print('Testing {f1} and {f2} return same results'.format(
            f1=f1.func_name,
            f2=f2.func_name))
        if not all([a==b for a,b in itertools.izip_longest(f1(num),f2(num))]):
            sys.exit("Error: %s(%s) != %s(%s)"%(f1.func_name,num,f2.func_name,num))

    n=1000000
    test(sieveOfAtkin,sieveOfEratosthenes,n)
    test(sieveOfAtkin,ambi_sieve,n)
    test(sieveOfAtkin,ambi_sieve_plain,n) 
    test(sieveOfAtkin,sundaram3,n)
    test(sieveOfAtkin,sieve_wheel_30,n)
    test(sieveOfAtkin,primesfrom3to,n)
    test(sieveOfAtkin,primesfrom2to,n)
    test(sieveOfAtkin,rwh_primes,n)
    test(sieveOfAtkin,rwh_primes1,n)         
    test(sieveOfAtkin,rwh_primes2,n)

tüm uygulamaların aynı sonucu verdiği komut dosyası testlerini çalıştırıyor.

324
cevap unutbu 2017-05-23 14:55:05
kaynak

ilgili soru(asal jeneratörlerle uğraşmak ve kriterler dahil):

Python'da bitstring / bit işlemlerini hızlandırmak mı?

ByteArray kullanarak bir python 3 sürümleri için

& bkz sıkıştırmak: https://stackoverflow.com/a/46635266/350331

daha hızlı ve daha fazla bellek bilge saf Python kodu:

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]]

veya yarım elek ile başlayan

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]]

daha hızlı ve daha fazla bellek bilge numpy kodu:

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

bir elek üçte biri ile başlayan daha hızlı bir varyasyon:

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)]

yukarıdaki kodun saf python sürümü

olacaktır
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]]

ne yazık ki saf-python, atama yapmanın daha basit ve daha hızlı uyuşuk yolunu kabul etmiyor ve [False]*len(sieve[((k*k)/3)::2*k]) deki döngü içinde len() çağırıyor çok yavaş. Bu yüzden doğaçlama yapmak zorunda kaldım doğru giriş (&daha fazla matematik kaçının) ve bazı aşırı (& ağrılı) matematik-büyü yapmak.

Şahsen, numpy'nin (çok yaygın olarak kullanılan) python standart kütüphanesinin bir parçası olmadığı(python 3 sürümünden 2 yıl sonra & numpy uyumluluğu yok) bir utanç olduğunu düşünüyorum ve sözdizimi ve hızdaki gelişmelerin python geliştiricileri tarafından tamamen göz ardı edildiğini düşünüyorum.

114
cevap Robert William Hanks 2018-10-02 21:49:37
kaynak

Python yemek kitabından oldukça düzgün bir örnek var burada - bu URL'de önerilen en hızlı sürüm:

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

böylece

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

bu kodla kabuk isteminde (yapmayı tercih ettiğim gibi) ölçüm yapıyor pri.py, dikkat ediyorum:

$ 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

bu yüzden yemek kitabı çözümü iki kat daha hızlı bitti gibi görünüyor.

41
cevap Alex Martelli 2015-07-16 16:33:40
kaynak

kullanarak Sundaram'ın eleği , sanırım saf-Python'un kaydını kırdım:

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)

karşılaştırması:

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
29
cevap jbochi 2010-01-20 14:11:19
kaynak

algoritma hızlıdır, ancak ciddi bir kusura sahiptir:

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

, numbers.pop() sette en küçük sayıyı döndüreceğini varsayıyorsunuz, ancak bu hiç garanti edilmiyor. Kümeler sırasız ve pop() kaldırır ve öğesi döndürür, bu nedenle kalan sayılardan bir sonraki asal seçmek için kullanılamaz.

18
cevap sth 2010-01-15 03:14:04
kaynak

için gerçekten yeterince büyük N ile en hızlı çözüm primes önceden hesaplanan listesini indirmek için olurdu , bir tuple olarak saklamak ve gibi bir şey yapmak:

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

Eğer N > primes[-1] sadece sonra daha fazla asal hesaplamak ve kodunuzda yeni liste kaydetmek, bu yüzden bir dahaki sefere eşit hızlı.

her zaman kutunun dışında düşünüyorum.

16
cevap Kimvais 2010-01-15 10:58:18
kaynak

tekerleği yeniden icat etmek istemiyorsanız, sembolik matematik kütüphanesini sympy (Evet Python 3 uyumlu)

yükleyebilirsiniz
pip install sympy

ve primerange işlev

kullanın
from sympy import sieve
primes = list(sieve.primerange(1, 10**6))
10
cevap Colonel Panic 2015-07-20 12:06:05
kaynak

kendi asal bulma kodunuzu yazmak öğretici, ancak eldeki hızlı güvenilir bir kütüphaneye sahip olmak da yararlıdır. 151930920 'C++ kütüphanesi primesieve etrafında bir sarıcı yazdım, primesieve-python

adını verdim

deneyin pip install primesieve

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

hızı karşılaştırmayı merak ediyorum.

6
cevap Colonel Panic 2015-07-20 12:06:46
kaynak

itertools'u kabul ederseniz ancak numpy değil, burada makinemde yaklaşık iki kat daha hızlı çalışan Python 3 için rwh_primes2'nin bir uyarlaması var. Tek önemli değişiklik, boolean için bir liste yerine bir bytearray kullanıyor ve son listeyi oluşturmak için bir liste yerine sıkıştırmak kullanıyor. (Bunu yapabilseydim moarningsun gibi bir yorum olarak eklerdim.)

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

karşılaştırmalar:

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

ve

>>> 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
6
cevap Jason 2016-02-28 19:14:14
kaynak

Miller-Rabin'in ilkel testinin n < 9,080,191

varsayımına ilişkin deterministik bir uygulaması
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)
Wikipedia makalesine göre

( http://en.wikipedia.org/wiki/Miller-Rabin_primality_test ) a = 2,3,37 için n < 9,080,191'i test edin ve n'nin kompozit olup olmadığına karar vermek yeterlidir.

ve kaynak kodunu orijinal Miller-Rabin'in olasılıksal uygulamasından uyarladım test burada bulundu: http://en.literateprograms.org/Miller-Rabin_primality_test_ (Python)

4
cevap Ruggiero Spearman 2010-01-21 03:17:45
kaynak

N üzerinde kontrolünüz varsa, tüm asal sayıları listelemenin en hızlı yolu bunları önceden belirlemektir. Gerçekten. Precomputing optimizasyon bir yoludur.

4
cevap Dave W. Smith 2010-01-21 03:21:40
kaynak

İşte normalde Python'da asal üretmek için kullandığım kod:

$ 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)

burada yayınlanan daha hızlı çözümlerle rekabet edemez, ancak en azından saf python.

bu soruyu yayınladığınız için teşekkürler. Bugün çok şey öğrendim.

4
cevap MAK 2010-01-21 19:09:36
kaynak
En hızlı kod için

, numpy çözümü en iyisidir. Tamamen akademik nedenlerden dolayı, yukarıda yayınlanan yemek kitabı sürümünden %50 daha hızlı olan saf python sürümümü yayınlıyorum. Tüm listeyi bellekte yaptığım için, her şeyi tutmak için yeterli alana ihtiyacınız var, ancak oldukça iyi ölçeklendirilmiş gibi görünüyor.

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)

ve sonuçlar:

>>>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
3
cevap Daniel G 2010-01-15 10:41:25
kaynak

Numpy kullanarak yarım elek biraz farklı bir uygulama:

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)

birisi bunu diğer zamanlamalarla karşılaştırabilir mi? Makinemde diğer uyuşuk yarı elekle oldukça karşılaştırılabilir görünüyor.

3
cevap nolfonzo 2010-09-03 22:37:02
kaynak

hepsi yazılı ve test edilmiştir. Yani tekerleği yeniden icat etmeye gerek yok.

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

bize bir rekor kırarak verir 12.2 msec !

10 loops, best of 10: 12.2 msec per loop

bu yeterince hızlı değilse, Pypy'yi deneyebilirsiniz:

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

hangi sonuçlarla sonuçlanır:

10 loops, best of 10: 2.03 msec per loop

247 Yukarı oy ile cevap en iyi çözüm için 15.9 ms listeler. Bunu karşılaştırın!!!

3
cevap lifolofi 2016-10-06 00:36:54
kaynak

işte en hızlı işlevlerden birinin iki güncellenmiş (saf Python 3.6) versiyonu,

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:])]
3
cevap Bruno Astrolino 2017-10-09 01:04:23
kaynak

python kullanarak ilk kez, bu yüzden bazı yöntemler bu kullanmak biraz hantal görünebilir. Sadece C++ kodumu python'a dönüştürdüm ve bu benim (python'da tad bit slowww olsa da)

#!/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

12.799119 saniye içinde 664579 asal bulundu!

#!/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

bulundu 664579 10.230172 saniye içinde asal!

#!/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

7.113776 saniye içinde 664579 asal bulundu!

2
cevap smac89 2013-02-21 03:12:55
kaynak

yarışmanın birkaç yıldır kapalı olduğunu biliyorum. ...

yine de bu, eleği ileri doğru işlerken uygun adımları kullanarak 2, 3 ve 5 katlarını atlamaya dayanan saf bir python asal elek için önerim. Bununla birlikte, n<10^9 için @Robert William Hanks superior solutions rwh_primes2 ve rwh_primes1'den daha yavaştır. Ctypes kullanarak.c_ushort elek dizisi 1.5 * 10 ^ 8'in üstünde bir şekilde bellek sınırlarına uyarlanabilir.

10^6

$ python-mtimeit-s "ithalat primeSieveSpeedComp "" primeSieveSpeedComp.primeSieveSeq (1000000)" 10 döngü, döngü başına en iyi 3: 46.7 msec

karşılaştırmak için: $ python-mtimeit-s " ithalat primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes1( 1000000) " 10 döngü, en iyi 3: 43.2 döngü başına MSN karşılaştırmak için: $ python-m timeıt-s " ithalat primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes2( 1000000) " 10 döngü, en iyi 3: 34.5 151920920 döngü başına MSN '

10^7

$ python-mtimeit-s "ithalat primeSieveSpeedComp "" primeSieveSpeedComp.primeSieveSeq (10000000)" 10 döngü, en iyi 3: 530 döngü başına msec

karşılaştırmak için: $ python-mtimeit-s " ithalat primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes1( 10000000) " 10 döngü, en iyi 3: 494 döngü başına MSN karşılaştırmak için: $ python-m timeıt-s " ithalat primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes2( 10000000) " 10 döngü, en iyi 3: 375 151920920 döngü başına MSN '

10^8

$ python-mtimeit-s "ithalat primeSieveSpeedComp "" primeSieveSpeedComp.primeSieveSeq (1000000)" 10 döngü, en iyi 3: döngü başına 5.55 sn

karşılaştırmak için: $ python-mtimeit-s " ithalat primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes1( 1000000) " 10 döngü, en iyi 3: 5.33 döngü başına sn için karşılaştırmak: $ python-m timeıt-s " ithalat primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes2( 1000000) " 10 döngü, en iyi 3: 3.95 döngü başına sn

10^9

$ python-mtimeit-s "ithalat primeSieveSpeedComp "" primeSieveSpeedComp.primeSieveSeq (100000000000)" 10 döngü, en iyi 3: 61.2 döngü başına sn

karşılaştırmak için: $ python-mtimeit-n 3-s " ithalat primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes1( 100000000000) " 3 döngüler, en iyi 3: 97.8 döngü başına sn

karşılaştırmak için: $ python-m timeit-s " ithalat primeSieveSpeedComp" "primeSieveSpeedComp.rwh_primes2 (100000000000) " 10 döngü, en iyi 3: Döngü başına 41.9 sn

bu testleri gözden geçirmek için ubuntus primeSieveSpeedComp içine aşağıdaki kodu kopyalayabilirsiniz.

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
2
cevap ABri 2013-09-25 11:33:23
kaynak

bazı test unutbu fonksiyonları , ben hungred milyonlar numarası ile hesaplanan

kazananlar, numpy kütüphanesini kullanan işlevlerdir,

not : ayrıca ilginç bir bellek kullanımı testi yapmak:)

Computation time result

örnek kod

github depomdaki komple kod

#!/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-46484/"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()
2
cevap Bruno Adelé 2017-05-23 15:10:30
kaynak

İçin 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]]
2
cevap SmartManoj 2017-07-19 15:03:37
kaynak

tahminim, ve her yönden, kodunuzdaki asal sayıları sabit bir şekilde kodlamaktır.

öyleyse neden sadece tüm sayıları sabitlenmiş olan başka bir kaynak dosyası üreten yavaş bir komut dosyası yazmıyorsunuz ve gerçek programınızı çalıştırdığınızda o kaynak dosyasını içe aktarıyorsunuz.

tabii ki, bu yalnızca derleme zamanında n'nin üst sınırını biliyorsanız çalışır, ancak bu nedenle (neredeyse) tüm proje Euler sorunları için geçerlidir.

PS: kaynağı sabit kablolu asal sayılarla ayrıştırmanın ilk etapta hesaplamaktan daha yavaş olmasına rağmen yanlış olabilirim, ancak bildiğim kadarıyla Python derlenmiş .pyc dosyalarından çalışır, bu nedenle n'ye kadar tüm asal sayılarla ikili bir dizi okumak bu durumda çok hızlı olmalıdır.

0
cevap akuhn 2010-01-25 04:26:22
kaynak

rahatsız ettiğim için üzgünüm ama erat2 () algoritmada ciddi bir kusur var.

bir sonraki kompozit ararken, biz sadece tek numaraları test etmek gerekir. q, p her ikisi de garip; daha sonra Q + p eşit ve test edilmesi gerekmez, ancak q + 2 * p her zaman gariptir. Bu, while döngü koşulundaki "If even" testini ortadan kaldırır ve çalışma süresinin yaklaşık %30'unu kaydeder.

biz oradayken: zarif 'D. pop(q,None)' get and delete method use 'ıf Q in D yerine' D pop (Q, None) 'get and delete method use' ıf Q in D: p = d[q],del d [q]' iki kat daha hızlı! En azından makinemde (P3-1Ghz). Bu yüzden bu akıllı algoritmanın bu uygulanmasını öneriyorum:

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
0
cevap user1016274 2010-08-13 16:04:55
kaynak

şimdiye kadar denediğim en hızlı yöntem Python yemek kitabı erat2 işlevine dayanıyor:

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

bkz bu hız-up bir açıklama için cevap.

0
cevap tzot 2017-05-23 15:10:30
kaynak

partiye geç kalabilirim ama bunun için kendi kodumu eklemek zorunda kalacağım. Uzayda yaklaşık n/2 kullanıyor çünkü sayıları bile saklamaya gerek yok ve bitarray python modülünden de yararlanıyorum, bellek tüketimini daha da büyük ölçüde kesiyorum ve 1,000.000.000

ye kadar tüm asal sayıları hesaplamayı sağlıyor
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

bu, 64bit 2.4 GHZ MAC OSX 10.8.3

üzerinde çalıştırıldı
0
cevap cobie 2013-05-20 14:56:19
kaynak

zamanla birkaç asal sayı eleği topladım. Bilgisayarımdaki en hızlı şudur:

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
0
cevap Stefan Gruenwald 2014-11-03 00:39:27
kaynak

bu soruya yavaş yanıt veriyorum ama eğlenceli bir egzersiz gibi görünüyordu. Hile yapan numpy kullanıyorum ve bu yöntemin en hızlı olduğundan şüpheliyim, ancak açık olmalıdır. Sadece endekslerine atıfta bulunan bir Boole dizisini eliyor ve tüm gerçek değerlerin endekslerinden asal sayıları ortaya çıkarıyor. Modulo gerek yok.

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]
0
cevap Alan James Salmoni 2015-02-16 01:16:14
kaynak

burada python'un liste kavrayışlarını kullanarak asal sayılar (ancak en verimli değil) üretmek için ilginç bir tekniktir:

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]

örnek ve bazı açıklamalar sağ bulabilirsiniz burada

0
cevap Alexander 2018-02-06 17:10:27
kaynak

genel olarak hızlı sayı hesaplamasına ihtiyacınız varsa python en iyi seçim değildir. Bugün çok daha hızlı (ve karmaşık) algoritma var. Örneğin bilgisayarımda kodunuz için 2.2 saniyem var, Mathematica ile 0.088005 aldım.

her şeyden önce: set ihtiyacınız var mı?

-1
cevap Ruggero Turra 2010-01-15 02:56:33
kaynak

bu, saklanan bir liste kullanarak asal bulmak için zarif ve basit bir çözümdür. Bir 4 değişken ile başlar, sadece bölenler için tek asal test etmek zorunda, ve sadece bir asal olarak test ne sayı bir yarısına kadar test etmek zorunda (test hiçbir nokta olup olmadığını 9, 11, 13 17 bölmek). Bu bölen olarak daha önce saklanan asal sınar.

    # 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
-2
cevap user3261711 2014-02-02 04:41:24
kaynak

bu başkalarıyla karşılaştırabilirsiniz yoludur.

# 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

çok basit...

-3
cevap lavee_singh 2015-07-18 16:19:07
kaynak

Diğer sorular python math optimization primes