10^9に近い範囲の素数を効率的に見つける^ 9

Question

範囲は[10^9-10^6 tiill 10^9]です。 Eratosthenesの篩で事前計算し、FermatのPrimality Testで事前にチェックしてみると、私が見つけて考えることができるすべてを試しました。しかし、まだ1分以内にそれを完了することができませんでした。

Answer 1

範囲は10^6であるためです。私が思うのは、シーブはそれほど悪くないはずだということです。
最初に1と10^5の間のすべての素数を生成します（10^5の平方は10^10で、最大数は10^9です）。
そして、次のようにsieveを使用します。
サイズが10^9-10^6 + iの意味で、サイズが10^6の配列を作成し、プライムリストを使用してすべての非素数を切り捨てます。 Sieveを使用している間は、最初はすべての偶数を掛けなければなりません。そして、あなたは2〜10^5の範囲に5000個の素数しかありません。だから、全体的にはおよそ10^3 * 10^6で10^9ステップです。モダンプロセッサの実行時間は非常に複雑ではありません。

Answer 2

これは、MacBook Proで約28秒で実行されます。あなたが欲しい素数は、これが第二もかからprimes

import math 

def isPrime(n, primes): 
    limit = int(math.sqrt(n)) 
    for i in primes: 
     if i > limit: 
     return True 
     if n % i == 0: 
     return False 
    return True 

low_primes = [2] 
for i in range(3, 10**5, 2): 
    if isPrime(i, low_primes): 
     low_primes.append(i) 

primes = [] 
for i in range(10**9-10**6 + 1, 10**9, 2): 
    if isPrime(i, low_primes): 
     primes.append(i) 

Answer 3

にあります

Python 2.7.10 (default, Jun 1 2015, 18:05:38) 
[GCC 4.9.2] on cygwin 
Type "help", "copyright", "credits" or "license" for more information. 
>>> def primegen(start=0): # stackoverflow.com/a/20660551 
...  if start <= 2: yield 2 # prime (!) the pump 
...  if start <= 3: yield 3 # prime (!) the pump 
...  ps = primegen()   # sieving primes 
...  p = next(ps) and next(ps) # first sieving prime 
...  q = p * p; D = {}   # initialization 
...  def add(m, s):   # insert multiple/stride 
...   while m in D: m += s # find unused multiple 
...   D[m] = s    # save multiple/stride 
...  while q <= start:   # initialize multiples 
...   x = (start // p) * p # first multiple of p 
...   if x < start: x += p # must be >= start 
...   if x % 2 == 0: x += p # ... and must be odd 
...   add(x, p+p)   # insert in sieve 
...   p = next(ps)   # next sieving prime 
...   q = p * p    # ... and its square 
...  c = max(start-2, 3)  # first prime candidate 
...  if c % 2 == 0: c += 1  # must be odd 
...  while True:    # generate infinite list 
...   c += 2    # next odd candidate 
...   if c in D:   # c is composite 
...    s = D.pop(c)  #  fetch stride 
...    add(c+s, s)  #  add next multiple 
...   elif c < q: yield c # c is prime; yield it 
...   else: # (c == q)  # add p to sieve 
...    add(c+p+p, p+p) #  insert in sieve 
...    p = next(ps)  #  next sieving prime 
...    q = p * p   #  ... and its square 
... 
>>> ps = primegen(10**9-10**6) 
>>> p = next(ps) 
>>> result = [] 
>>> while p < 10**9: 
...  result.append(p) 
...  p = next(ps) 
... 
>>> print len(result) 
47957 

は、説明のためにhttps://programmingpraxis.com/2015/07/31/incremental-sieve-of-eratosthenes/を参照してください。

Answer 4

ありがとうございます！私はあなたの答えを後でチェックし、自分でそれを行う方法を理解します。逆の順序でメソッドを適用します。最初のFermat、次にEratosphenです。 2〜3秒かかります。

n = 999000000 
#n = 1 # should be 78499 
m = n + 1000000 


def eratosphene_filter(sorted_array_of_odd): 
    biggest = sorted_array_of_odd[-1] 
    smallest = sorted_array_of_odd[0] 
    mapping ={i:True for i in sorted_array_of_odd} 
    for i in range(3, int(biggest**0.5)+1, 2): 
     j = nearest_from_bottom = (smallest // i) * i 
     while j < biggest: 
      if i!=j and j in mapping: 
       mapping[j] = False 
      j += i 

    result = [] 
    for k,v in mapping.items(): 
     if v: 
      result.append(k) 
    return sorted(result) 


def fermat_check(x, d=2): 
    return pow(d, x-1, x) == 1 


def primes_sieve(lower,top): 
    if lower < 3: 
     yield 1 
     yield 2 
     lower = 3 

    all_numbers_in_range = range(lower if lower % 2 != 0 else lower + 1, top, 2) 
    print(len(all_numbers_in_range)) 
    probably_primes = list(filter(fermat_check, all_numbers_in_range)) 
    print(len(probably_primes)) 
    print(probably_primes[:5],'...',probably_primes[-5:]) 

    primes_for_sure = list(eratosphene_filter(probably_primes)) 
    print(len(primes_for_sure)) 
    for i in primes_for_sure: 
     yield i 


found_primes = list(primes_sieve(n, m)) 

print(found_primes[:5],'...',found_primes[-5:]) 

print(len(found_primes))