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

smgp

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

1. #include <stdio.h>
   
2. #define M 100000
   
3. 
   
4. bool mark[M];
   
5. 
   
6. void init()
   
7. {
   
8.         for(int i = 1; i < M;i++)
   
9.         {
   
10.                 mark[i] = false;//初始化均未标记
    
11.         }
    
12.         for (int i = 2; i < M; i++)
    
13.         {
    
14.                 if(mark[i] == true)
    
15.                 {//如果是非素数
    
16.                         continue;
    
17.                 }
    
18.                 for(int j = i * i; j < M; j = j + i)
    
19.                 {
    
20.                         mark[j] = true;//将素数的倍数标记为非素数
    
21.                 }
    
22.         }
    
23. }
    
24. 
    
25. int main()
    
26. {//求第k个素数
    
27.         init();
    
28.         int n;
    
29.         while(scanf("%d",&n) != EOF)
    
30.         {
    
31.                 for (int i = 2; i < M; i++)
    
32.                 {
    
33.                         if(mark[i] == false)
    
34.                         {//该数为素数
    
35.                                 n--;
    
36.                                 if(!n)
    
37.                                 {
    
38.                                         printf("%d\n",i);
    
39.                                 }
    
40.                         }
    
41.                 }
    
42.         }
    
43.         return 0;
    
44. }

复制代码

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

1. #include<iostream>  
   
2. #include<string.h>  
   
3. #include<stdio.h>  
   
4. using namespace std;  
   
5. #define M 1000010  
   
6. bool flag[M];  
   
7. int prime[M];  
   
8. void getprime()  
   
9. {  
   
10.     int cnt=1;  
    
11.     for(int i=2;i<M;++i)  
    
12.     {  
    
13.         if(!flag[i])  
    
14.         {  
    
15.             prime[cnt++]=i;  
    
16.             for(int j=i;j<M;j+=i)  
    
17.                 flag[j]=true;  
    
18.         }  
    
19.     }  
    
20. }  
    
21. int main(int argc, char *argv[])  
    
22. {  
    
23.     int k;  
    
24.     // freopen("1040.in","r",stdin);  
    
25.     getprime();  
    
26.     prime[0]=0;  
    
27.     while(scanf("%d",&k)!=EOF)  
    
28.     {  
    
29.         printf("%d\n",prime[k]);  
    
30.     }  
    
31.     return 0;  
    
32. }  

复制代码

小甲鱼

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 ...

哦哦哦，蟹蟹。。