用筛法求之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.

#include <stdio.h>

int main(void)
{
        int N  , a , b[50000] , c  , i       ;
        scanf("%d" , & N)                    ;
        for(i = 2 ; i < N + 1 ; i ++) {
                a = 2                        ; // 很有必要，对于每一个 i 都必须初始化
                c = 0                        ; // 很有必要，对于每一个 i 都必须初始化
                while(a * a < i + 1)           // 不必循环到 a = i,根据乘法交换律，只需要循环一半次数即可
                {
                        b[c] = i % a         ;
                        a ++                 ;
                        c ++                 ;
                }
                for(a = 0 ; a < c ; a ++)      // 一共产生了 c 个余数
                {
                        if(b[a] == 0) break  ; // 如果有余数为 0 值，说明 i 不是素数，中断循环
                }
                if(a == c) printf(" %d" , i) ; // 如果循环是正常结束的，说明没有找到 0 值余数，那 i 就是素数无疑
        }
}

2.

#include <stdio.h>
int Is(int num)
{
                int i;
                for(i = 2; i < num; i++)
                {
                        if(num % i == 0)
                        {
                                return 0;
                        }
                }
                return 1;
}

main()
{
        int N, i, n = 0;
        scanf("%d",&N);
        int b[N]; // 最好在给N赋值后 
        for(i=2;i<=N;i++)
        {
                if(Is(i))
                {
                        b[n++] = i;
                }
        }
        
        for(i = 0; i < n; i++)
        {
                printf("%d ", b[i]);
        }
        
 }