1

特定の開始値「N」より上の素数の「M」個をリストする関数を書いています。この時点で、関数をできるだけ効率的にしたいと思います（つまり、FAST！）。私は本当にアイデアがないので、どんな助けでも大歓迎です。コード（matlab）は次のとおりです。

function PrimeNumbersList = primes_after(N,M)
tic;
x = N;
s = 1;
PrimeNumbersList = 0;
if mod(N,2) == 0
while numel(PrimeNumbersList) < M

if isprime(x) == 1
    PrimeNumbersList(s) = x;
    x=x+2;
    s=s+1;
else
    x=x+2;
end
end
else
while numel(PrimeNumbersList) < M

if isprime(x) == 1
    PrimeNumbersList(s) = x;
    x=x+1;
    s=s+1;
else
    x=x+1;
end 
end
end
tElapsed=toc
end
4

3 に答える 3

1

できることの 1 つは、奇数のみを考慮することです (1 ではなく 2 ずつ増やします)。これにより、ループの反復回数が半分になります。

実装方法によっては、 で得られる可能性がありますisprime。それはすべて、どれだけ正確である必要があるかによって異なります (つまり、カーマイケル数は許可されていますか?)。

編集：

あなたの編集は実際には何も修正しませんでした。代わりにこれを試してください：

function PrimeNumbersList = primes_after(N,M)
    tic;
    x = N;
    s = 1;
    PrimeNumbersList = 0;

    if mod(x,2) == 0
        if x == 2
            PrimeNumbersList(s) = x;
            s=s+1;
        end
        x=x+1;
    end

    while numel(PrimeNumbersList) < M
        if isprime(x) == 1
            PrimeNumbersList(s) = x;
            s=s+1;
        end
        x=x+2;
    end

    tElapsed=toc
end

また、おそらく関数呼び出しに変更numel(PrimeNumberList) < Mしs < mて回避できます。マイナーな最適化ですが、すでに髪を分割しています。

編集：

エラーを受け入れることができない場合 (たとえば、カーマイケル数)、isprime(それが正しいと仮定して) の遅い実装に行き詰まっています。これは、数値が素数かどうかを確認するのが難しいためです。Fermat s Little Theorem is a clever shortcut, butisprime` はおそらくエラーを排除するための追加の検証とともにそれを使用します。

他にできることはほとんどありません。これを別の言語で書き直すつもりなら、Haskell をお勧めします。数値を生成するための優れたサポートがあり、コードを約 3 行の関数 (またはその程度) に変換します。

私はいくつかの余分なサイクルを排除するのに十分なほどmatlabを知りませんが、ここにいくつかの提案があります:

  • matlab が PrimeNumbersList に追加できる場合は、インデックスを設定する代わりにそれを行います。これはより速いかもしれません（Javascriptです）
    • これによりs変数が削除されるため、追加が不要になります
  • sの代わりに使用しますnumel(上記の試みの代わりにこれを試してください)
于 2012-11-26T02:20:03.653 に答える
1

ここでは、速度が向上する可能性がいくつかあります。

function PrimeNumbersList = primes_after(N,M)
tic;

x = 0;
if (N mod 2) == 0 && N != 2
    x = N + 1;
else
    x = N;
end

s = 1;
PrimeNumbersList = 0;
tempInt = x - 1;
isPrime = 1;

while numel(PrimeNumbersList) < M

    while tempInt > 1 && isPrime
        if (x mod tempInt) == 0
            isPrime = 0;
        end
        tempInt=tempInt-1;
    end

    if isPrime
        PrimeNumbersList(s) = x;
        x=x+1;
        s=s+1;
    else
        x=x+1;
    end

end
tElapsed=toc
end

さて、説明のために：

まず、Nが偶数かどうかを調べます。もしそうなら、それが奇数であることを確認するためだけに 1 をインクリメントします (必ずしも素数ではありません)。整数 2 は素数ですが、2 で割り切れます。

私は isPrime() の速度がわからないので、(素数の簡単な証明に基づいて) 自分で書きました。tic/toc で確認してみてください。

それ以外には、私が見ることができる速度の増加はあまりありません。私の2セント。

于 2012-11-26T02:43:29.083 に答える
0

それぞれ素数をテストする数値のセットを反復処理しないでください。それは信じられないほど遅くなります。あなたが探しているアルゴリズムは、エラトステネスのセグメントふるいと呼ばれます。

エラトステネスのふるいは非常に高速ですが、O(n) のスペースが必要です。これは、連続するセグメントでふるい分けを実行することにより、ふるい素数の O(sqrt(n)) と bitarray の O(1) に減らすことができます。最初のセグメントでは、セグメント内にある各ふるい素数の最小倍数が計算され、ふるい素数の倍数が通常の方法で合成としてマークされます。すべてのふるい素数が使用されると、セグメント内の残りのマークされていない数が素数になります。次に、次のセグメントでは、各ふるい素数の最小倍数は、前のセグメントでふるい分けを終了した倍数であるため、ふるい分けは終了するまで続行されます。

20 のセグメントで 100 から 200 までふるい分ける例を考えてみましょう。5 つのふるい素数は 3、5、7、11、13 です。100 から 120 までの最初のセグメントでは、bitarray には 10 個のスロットがあり、スロット 0 は 101 に対応し、スロット k は 100 + 2k - 1 に対応し、スロット 9 に対応します。セグメント内の最小の 3 の倍数は 105 で、スロット 2 に対応します。スロット 2+3=5 および 5+3=8 も 3 の倍数です。5 の最小の倍数はスロット 2 で 105 であり、スロット 2+5=7 も 5 の倍数です。7 の最小の倍数は 105 です。スロット 2 では、スロット 2+7=9 も 7 の倍数です。

関数 primes は、引数 lo、hi、および delta を取ります。lo と hi は、lo < hi で偶数でなければならず、lo は、ceiling(sqrt(hi)) よりも大きくなければなりません。セグメント サイズはデルタの 2 倍です。長さ m の配列 ps には、sqrt(hi) より小さいふるい素数が含まれます。偶数は無視されるため、2 が削除されます。配列 qs には、対応するふるい素数の現在のセグメント内の最小倍数のふるい bitarray へのオフセットが含まれます。各セグメントの後、lo はデルタの 2 倍進むため、ふるいビット配列のインデックス j に対応する数値は、lo + 2j + 1 です。

function primes(lo, hi, delta)
  sieve := makeArray(0..delta-1) # bitarray
  # calculate m and ps as described in text
  qs := makeArray(0..m-1) # least multiples
  for i from 0 to m-1
    qs[i] := (-1/2 * (lo + ps[i] + 1)) % ps[i]
  while lo < hi
    for i from 0 to delta-1
      sieve[i] := True
    for i from 0 to m-1
      for j from qs[i] to delta step ps[i]
        sieve[j] := False
      qs[i] := (qs[i] - delta) % ps[i]
    for i from 0 to delta-1
      t := lo + 2*j + 1
      if sieve[i] and t < hi
        output t
    lo := lo + 2*delta

上記の例では、これは素数 (100, 200, 10) と呼ばれます。上記の例では、qs は最初は [2,2,2,10,8] であり、最小の倍数 105、105、105、121、および 117 に対応し、2 番目のセグメントでは [1,2,6, 0,11]、最小の倍数 123、125、133、121、および 143 に対応します。このアルゴリズムは非常に高速です。1 秒以内に数百万の素数を生成できるはずです。

素数を使ったプログラミングについて詳しく知りたい場合は、私のブログでこのエッセイをお勧めします。

于 2012-11-26T13:46:30.157 に答える