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