1

10 分間の作業の後、以下に示す関数を作成しました。引数より下位のすべての素数のリストを返します。この関数を可能な限り高速にするために、私が知っているすべてのプログラミングと数学的トリックを使用しました。100 万未満の素数をすべて見つけるには、約 2 秒かかります。

さらに最適化する可能性はありますか? 何か案は？

def Primes(To):
  if To<2:
    return []
  if To<3:
    return [2]
  Found=[2]
  n=3
  LastSqr=0
  while n<=To:
     k=0
     Limit=len(Found)
     IsPrime=True
     while k<Limit:
         if k>=LastSqr: 
            if Found[k]>pow(n,0.5): 
               LastSqr=k
               break
         if n%Found[k]==0:
            IsPrime=False
            break
         k+=1
     if IsPrime:
        Found.append(n)
     n+=1
  return Found
4

3 に答える 3

5

エラストテンの基本的なふるいを使用して、いくつかのトリックを使用して速度を上げることができます。1 つは、Wheel Factorizationを使用して、素数ではないことがわかっている数値の計算をスキップすることです。たとえば、2 と 3 を除いて、すべての素数は 1 または 5 mod 6 に一致します。これは、6 つの数ごとに 4 つを処理する必要がないことを意味します。

次のレベルでは、すべての素数は 1、7、11、13、17、19、23、または 29 (mod 30) に一致します。30 個の数字ごとに 22 個を捨てることができます。

以下は、偶数を計算または保存しないエラストテネスのふるいの簡単な実装です。

def basic_gen_primes(n):
    """Return a list of all primes less then or equal to n"""
    if n < 2:
        return []

    # The sieve.  Each entry i represents (2i + 1)
    size = (n + 1) // 2
    sieve = [True] * size

    # 2(0) + 1 == 1 is not prime
    sieve[0] = False

    for i, value in enumerate(sieve):
        if not value:
            continue

        p = 2*i + 1

        # p is prime.  Remove all of its multiples from the sieve
        # p^2 == (2i + 1)(2i + 1) == (4i^2 + 4i + 1) == 2(2i^2 + 2i) + 1
        multiple = 2 * i * i + 2 * i 
        if multiple >= size:
            break

        while multiple < size:
            sieve[multiple] = False
            multiple += p 

    return [2] + [2*i+1 for i, value in enumerate(sieve) if value]

前述のように、よりエキゾチックなふるいも使用できます。

于 2012-07-31T13:58:54.903 に答える
4

奇数のみ確認できます。では、n +=1の代わりにn+= 2を使用してみませんか？

于 2012-07-31T13:44:26.690 に答える
2

より良いアルゴリズムについては、google と wikipedia を参照してください。小さな素数だけを探しているのであれば、これで十分速いかもしれません。しかし、実際のアルゴリズムは素数が大きいほど高速です。

http://en.wikipedia.org/wiki/Quadratic_sieve

そのページから始めます。

n を 1 ではなく 2 ずつ増やします。?

于 2012-07-31T13:41:09.710 に答える