0

n 番目の正方形の自由半素数を見つけようとしていました (N <= 2 * 10^6)。私はそれをしようとする次のコードを持っています。ここで実行時エラーが発生し続けます。理由がわかりません。

これが私がやったことです。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 3000000

int main()
{
    bool* prime = new bool[N];
    int* primes = new int[N];
    int* semiprimes = new int[2000005];

    for(int i=0; i < N ; i++) prime[i] = true;
    int cnt = 0;
    for(int i=2 ; i < N ; i++)
    {
        if(prime[i])
        {
            primes[cnt++] = i;
            for(int j = i; j < N ; j+= i)
                prime[j] = false;
        }
    }

    int i, j, k = 1;
    int p, q, current_limit;
    int target = 2000000;
    for (i = 0, p = primes[i]; p < target; i++)
    {
        current_limit = target/p;
        for (j = i + 1, q = primes[j]; q <= current_limit; j++)
        {
            k++;
            semiprimes[k++] = p*q;
        }
    }
    printf("%d\n",k);

    int t;

    scanf("%d",&t);
    int n;
    while(t--)
    {
        scanf("%d",&n);
        printf("%d\n",semiprimes[n]);
    }

    delete[] prime;
    delete[] semiprimes;
    delete[] primes;

    return 0;
}

誰かが私が間違っていることを教えてください。

4

2 に答える 2

0

あなたはおそらく次のように二重の増分を望まないでしょうk：

    for (j = i + 1, q = primes[j]; q <= current_limit; j++)
    {
        k++;
        semiprimes[k++] = p*q;
    }

これは、配列の他のすべての要素のみが使用されることを意味します。おそらくk、制限がオーバーフローしていないか、配列の境界（などの値）も確認する必要があります。

于 2012-05-13T06:31:09.287 に答える
0

スタックに何百万もの要素を持つ複数の配列を割り当てようとしていますが、通常は数メガバイトに制限されています。次のようなものを使用して、代わりにヒープに割り当てる必要があります。

bool *prime = new bool[N];
int *primes = new int[N];
int *semiprimes = new semiprimes[2000005];

// Do everything you need...

delete[] prime;
delete[] primes;
delete[] semiprimes;
于 2012-05-13T05:00:59.830 に答える