筛法求素数，m一大程序就挂

smgp

这是我写的代码，M是10000就正常运行，为什么M是100000就不行。

#include <stdio.h>
#define M 100000

bool mark[M];

void init()
{
        for(int i = 1; i < M;i++)
        {
                mark[i] = false;//初始化均未标记 
        }
        for (int i = 2; i < M; i++)
        {
                if(mark[i] == true)
                {//如果是非素数 
                        continue;
                } 
                for(int j = i * i; j < M; j = j + i)
                {
                        mark[j] = true;//将素数的倍数标记为非素数 
                }
        }
}

int main()
{//求第k个素数 
        init();
        int n;
        while(scanf("%d",&n) != EOF)
        {
                for (int i = 2; i < M; i++)
                {
                        if(mark[i] == false)
                        {//该数为素数 
                                n--;
                                if(!n)
                                {
                                        printf("%d\n",i);
                                }
                        }
                }
        }
        return 0;
}

但是我看人家写的代码，数组也是开到一百万了都能正常运行，这是别人写的代码。

#include<iostream>  
#include<string.h>  
#include<stdio.h>  
using namespace std;  
#define M 1000010  
bool flag[M];  
int prime[M];  
void getprime()  
{  
    int cnt=1;  
    for(int i=2;i<M;++i)  
    {  
        if(!flag[i])  
        {  
            prime[cnt++]=i;  
            for(int j=i;j<M;j+=i)  
                flag[j]=true;  
        }  
    }  
}  
int main(int argc, char *argv[])  
{  
    int k;  
    // freopen("1040.in","r",stdin);  
    getprime();  
    prime[0]=0;  
    while(scanf("%d",&k)!=EOF)  
    {  
        printf("%d\n",prime[k]);  
    }  
    return 0;  
}  

小甲鱼

int 的取值范围（4 位的情况下）是 -2147483648 ~ 2147483647

代码中存在 i * i，i 的最大取值是 99999，结果是 9999800001 > 2147483647，所以……

jackche0214

不是很懂，帮顶

smgp

小甲鱼 发表于 2017-2-20 02:28
int 的取值范围（4 位的情况下）是 -2147483648 ~ 2147483647

代码中存在 i * i，i 的最大取值是 99999 ...

哦哦哦，蟹蟹。。