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

您正在尝试在堆栈中分配具有数百万个元素的多个数组，这通常限制为几兆字节。你应该在堆上分配，使用类似的东西：

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 回答
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 回答