4

nth(n <= 2000000)平方自由 半素数を見つけようとしています。そのための次のコードがあります。

 int k = 0;
for(int i = 0; i <= 1000; i++)
{
    for(int j = i +1 ; j <= 2500; j++ )
    {
        semiprimes[k++] = (primes[i]*primes[j]);
    }
}
 sort(semiprimes,semiprimes+k);

primes[]素数のリストです。

私の問題は、n = 2000000for ループの制限が異なり、 の値が異なることです。誰かがこれらの制限を正しく計算する方法を教えてもらえますか?

前もって感謝します..

4

2 に答える 2

2

n 番目の最初の準素数平方自由数を計算したいとします。「最初」は、特定の値の下でそれらすべてを生成する必要があることを意味します。あなたの方法は、これらの数値を大量に生成し、それらをソートし、n 番目の最初の値を抽出することで構成されます。

これは良い方法ですが、すべての数値を生成する必要があります。ネストされたループに 2 つの異なる制限を設定することは、それらのいくつかを見逃す良い方法です (この例では、primes[1001]*primes[1002]どれが にあるべきかを計算していませんsemiprimes)。

この問題を回避するには、すべての半素数を正方形で計算する必要があります。たとえば[1,L]*[1,L]、L は両方のループの制限です。

L を決定するために必要なのは、数えることだけです。N を の下の準素数平方自由数の数としprimes[L-1]*primes[L-1]ます。

N = (L * L - L) / 2

L*L は、ペアごとの乗算の合計数です。L は正方形の数です。これは、正しい数を得るために 2 を 2 で割ります (なぜならprimes[i]*primes[j] = primes[j]*primes[i])。

n<=N となるように L を選択します。したがって、 n = 2000000 の場合:

    int L = 2001, k = 0;
    for(int i = 0; i < L; i++)
    {
        for(int j = i+1 ; j < L; j++ )
        {
            semiprimes[k++] = (primes[i]*primes[j]);
        }
    }
    sort(semiprimes,semiprimes+k);
于 2012-05-24T14:09:58.603 に答える
0

ボックス内のすべての半素数を計算することによって機能するアプローチが、妥当な時間内に機能するとは思えません。最初の 200 万個の半素数の因数 (p,q) をグラフにするとします。グラフをより対称的にするために、(p,q) と (q,p) の両方の点をプロットしましょう。グラフはきれいな長方形の領域を形成しませんが、代わりに双曲線 y=1/x のように見えます。この双曲線はかなり遠くまで伸びており、これらを含む四角形全体を反復処理すると、多くの無駄な計算が行われます。

最初に「N 以下の準素数はいくつあるか」という問題を解決することを検討することをお勧めします。次に、バイナリ検索を使用します。各クエリは約 sqrt(N) ステップで実行できます (ヒント: 二分探索が再びヒットします)。確かに少なくとも 100 万、おそらくそれ以上の、かなり大きな素数のテーブルが必要になります。これは、ある程度の事前計算を行うことで、任意の大きな定数係数によって削減できますが。

于 2012-06-14T04:59:28.847 に答える