难以从大范围中筛选素数

Question

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

int main() {
    int t,m,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&m,&n);
        int rootn=sqrt(double(n));
        bool p[10000];      //finding prime numbers from 1 to square_root(n)
        for(int j=0;j<=rootn;j++)
            p[j]=true;
        p[0]=false;
        p[1]=false;
        int i=rootn;
        while(i--)
        {
            if(p[i]==true)
            {
                int c=i;
                do
                {
                    c=c+i;
                    p[c]=false;
                }while(c+p[i]<=rootn);
            }
        };
        i=0;
        bool rangep[10000]; //used for finding prime numbers between m and n by eliminating multiple of primes in between 1 and squareroot(n)
        for(int j=0;j<=n-m+1;j++)
            rangep[j]=true;
        i=rootn;
        do
        {
            if(p[i]==true)
            {
                for(int j=m;j<=n;j++)
                {
                    if(j%i==0&&j!=i)
                        rangep[j-m]=false;
                }
            }
        }while(i--);
        i=n-m;
        do
        {
            if(rangep[i]==true)
                printf("%d\n",i+m);
        }while(i--);
        printf("\n");
    }
    return 0;
    system("PAUSE");
}

您好，我正在尝试使用埃拉托色尼筛法在 m 到 n 之间的范围内查找素数，其中 m>=1 且 n<=100000000。当我输入 1 到 10000 时，结果是正确的。但是对于更大的范围，即使我增加数组大小，堆栈也会溢出。

Answer 1

出现错误的原因

你将一个巨大的数组声明为局部变量。这就是为什么当main的堆栈帧被压入时需要如此多的内存以致于产生堆栈溢出异常。 Visual studio 足以分析预计运行时间堆栈使用的代码并在需要时生成异常。

使用这个紧凑的实现。此外，如果需要，您可以在函数中声明 bs 。不要使实现变得复杂。

实施

typedef long long ll;
typedef vector<int> vi;
vi primes;
bitset<100000000> bs;
void sieve(ll upperbound) {         
  _sieve_size = upperbound + 1;                   
  bs.set();                                                 
  bs[0] = bs[1] = 0;                                     
  for (ll i = 2; i <= _sieve_size; i++) 
  if (bs[i]) {  //if not marked  

    for (ll j = i * i; j <= _sieve_size; j += i) //check all the multiples 
         bs[j] = 0; // they are surely not prime :-)

    primes.push_back((int)i); // this is prime 
} }

从 main() 调用 sieve(10000);。您在向量 primes.

中有素数列表

注意： 正如评论中提到的——Whosebug 在这里是非常意外的错误。您正在实施筛子，但如果您使用 bistet 而不是 bool.

会更有效率

很少有类似 if n=10^8 then sqrt(n)=10^4 这样的事情。你的 bool 数组是 p[10000]。所以有机会越界访问数组。

Answer 2

一个简单易读的实现

void Sieve(int n) {
    int sqrtn = (int)sqrt((double)n);
    std::vector<bool> sieve(n + 1, false);
    for (int m = 2; m <= sqrtn; ++m) {
        if (!sieve[m]) {
            cout << m << " ";
            for (int k = m * m; k <= n; k += m)
                sieve[k] = true;
        }
    }
    for (int m = sqrtn; m <= n; ++m)
        if (!sieve[m])
            cout << m << " ";
}

Answer 3

我同意其他答案，说你基本上应该重新开始。你甚至关心为什么你的代码不起作用？（你实际上并没有问。）

我不确定你的代码中的问题还没有被准确识别。首先，我将添加此评论以帮助设置上下文：

// For any int aardvark;
// p[aardvark] = false   means that aardvark is composite (i.e., not prime).
// p[aardvark] = true    means that aardvark might be prime, or maybe we just don’t know yet.

现在让我提请您注意这段代码：

        int i=rootn;
        while(i--)
        {
            if(p[i]==true)
            {
                int c=i;
                do
                {
                    c=c+i;
                    p[c]=false;
                }while(c+p[i]<=rootn);
            }
        };

你说 n≤100000000（虽然你的代码没有检查），所以，据推测，rootn≤10000，也就是p[]的维数（大小）。上面的代码是说，对于每个整数 i （无论是质数还是合数）， 2×i、3×i、4×i等，根据定义，都是合数。所以，对于 c 等于 2×i, 3×i, 4×i, …, 我们设置 p[c]=false 因为我们知道 c 是复合的。

但是仔细看代码。它设置 c=c+i 并表示 p[c]=false before 检查 c 是否仍在范围内成为 p[] 的有效索引。现在，如果 n≤25000000，则 rootn≤5000。若i≤rootn，则i≤5000，只要c≤5000，则c+i≤10000。但是，如果 n>25000000，则 rootn>5000，^† 以及序列 i=rootn;、c=i;、c=c+i; 可以将 c 设置为大于 10000 的值。然后您使用该值索引到 p[]。这可能是发生堆栈溢出的地方。

哦，顺便说一句；你不需要说 if(p[i]==true)； if(p[i]) 够用了。

雪上加霜的是，同一块中还有第二个错误： while(c+p[i]<=rootn)。 c和i是int_s, p 是 bool_s 的数组，所以 p[i] 是 bool — 然而你添加了c<sub> </sub>+<sub> </sub>p[i]。我们从 if 知道 p[i] 是 true, 在数值上等于 1 — 所以你的循环终止条件是 while (c+1<=rootn); 即，同时 c≤rootn-1。我想你的意思是 while(c+i<=rootn).

哦，还有，你怎么会有可执行代码在无条件 return 语句之后立即？不可能到达 system("PAUSE"); 语句。

（我并不是说这些是唯一的错误；他们正是我突然想到的。）
______________
^† OK，劈头盖脸，n必须≥‰25010001 （即 5001²）在 rootn>5000.

之前

难以从大范围中筛选素数

Trouble sieving primes from a large range

c++

stack

出现错误的原因

实施