c++ - 当我想要大于 1000000 的素数时，以下素数生成器代码显示错误。为什么？

Question

当我想要大于 1000000 的素数时，以下素数生成器代码显示错误。为什么？起初它似乎发生在 b'cuz of int 所以我把它改成 long 但错误仍然存​​在....从技术上讲它是一个错误程序运行后显示消息“primegen.exe 已停止工作”

#include <iostream>
using namespace std;
int main()
{
long int a,c,k,d;
k=0;
cin>>a;
cin>>d;
long int b[a];
b[a-1]=0;
for(long int i=2;i<=a;i++)
{
    for(long int j=2;j<=(i/2);j++)
    {
        c=1;
        if ( i%j!=0 )
        {
            continue;
        }    
        else 
        {
            c=0;
            break;
        }   
    }
    if (c!=0)
        {
             b[k]=i;
             //++k;
        }
    else b[k]=0;
    ++k;
 }
 for(long int i=d;i<a;i++)
 {
     if (b[i]!=0)
     {
          cout<<b[i]<<"\t";
     }         
 }   
 cin.ignore();
 cin.get();
 return 0;
 }          

Answer 1

这段代码没有错误。

代码太慢了，几乎是二次的。ideone 达到 100 万的预计时间：290 秒。

修复它后，通过将内部for循环条件从更改for(...;j<=(i/2);...)为for(...;j<=(i/j);...)，它在 Ideone 上以 ~ n^1.45 运行，并在 1.27 秒内达到 100 万。

Answer 2

Defining a static array won't help in this case. Because you're not allowed to declare such a long static array in C++; You might want to try

int *b = new int [a];

declaring the array size dynamically (i.e the array size will be decided at run time). The code should work until variable 'a' exceeds the range of int (–2,147,483,648 to 2,147,483,647).