用筛法求之N内的素数。

愷龍

题目描述
用筛法求之N内的素数。
输入
N
输出
0～N的素数
样例输入
100
样例输出
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
--------------
1.

1. #include <stdio.h>
   
2. 
   
3. int main(void)
   
4. {
   
5.         int N  , a , b[50000] , c  , i       ;
   
6.         scanf("%d" , & N)                    ;
   
7.         for(i = 2 ; i < N + 1 ; i ++) {
   
8.                 a = 2                        ; // 很有必要，对于每一个 i 都必须初始化
   
9.                 c = 0                        ; // 很有必要，对于每一个 i 都必须初始化
   
10.                 while(a * a < i + 1)           // 不必循环到 a = i,根据乘法交换律，只需要循环一半次数即可
    
11.                 {
    
12.                         b[c] = i % a         ;
    
13.                         a ++                 ;
    
14.                         c ++                 ;
    
15.                 }
    
16.                 for(a = 0 ; a < c ; a ++)      // 一共产生了 c 个余数
    
17.                 {
    
18.                         if(b[a] == 0) break  ; // 如果有余数为 0 值，说明 i 不是素数，中断循环
    
19.                 }
    
20.                 if(a == c) printf(" %d" , i) ; // 如果循环是正常结束的，说明没有找到 0 值余数，那 i 就是素数无疑
    
21.         }
    
22. }

复制代码

2.

1. #include <stdio.h>
   
2. int Is(int num)
   
3. {
   
4.                 int i;
   
5.                 for(i = 2; i < num; i++)
   
6.                 {
   
7.                         if(num % i == 0)
   
8.                         {
   
9.                                 return 0;
   
10.                         }
    
11.                 }
    
12.                 return 1;
    
13. }
    
14. 
    
15. main()
    
16. {
    
17.         int N, i, n = 0;
    
18.         scanf("%d",&N);
    
19.         int b[N]; // 最好在给N赋值后
    
20.         for(i=2;i<=N;i++)
    
21.         {
    
22.                 if(Is(i))
    
23.                 {
    
24.                         b[n++] = i;
    
25.                 }
    
26.         }
    
27.        
    
28.         for(i = 0; i < n; i++)
    
29.         {
    
30.                 printf("%d ", b[i]);
    
31.         }
    
32.        
    
33. }
    

复制代码