smgp 发表于 2017-2-20 00:07:47

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

这是我写的代码，M是10000就正常运行，为什么M是100000就不行。
#include <stdio.h>
#define M 100000

bool mark;

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

int main()
{//求第k个素数
        init();
        int n;
        while(scanf("%d",&n) != EOF)
        {
                for (int i = 2; i < M; i++)
                {
                        if(mark == 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;
int prime;
void getprime()
{
    int cnt=1;
    for(int i=2;i<M;++i)
    {
      if(!flag)
      {
            prime=i;
            for(int j=i;j<M;j+=i)
                flag=true;
      }
    }
}
int main(int argc, char *argv[])
{
    int k;
    // freopen("1040.in","r",stdin);
    getprime();
    prime=0;
    while(scanf("%d",&k)!=EOF)
    {
      printf("%d\n",prime);
    }
    return 0;
}

小甲鱼 发表于 2017-2-20 02:28:23

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

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

jackche0214 发表于 2017-2-20 11:14:06

不是很懂，帮顶{:10_266:}

smgp 发表于 2017-2-21 14:17:27

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

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

哦哦哦，蟹蟹。。
页: [1]
查看完整版本: 筛法求素数，m一大程序就挂