数组～筛法求素数

标签：筛法 int 样例 素数 数组 include

题目描述

用筛法求之N内的素数。 
用筛法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时结束。 

输入

N(N<1000)

输出

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>
 2 #include<math.h>
 3 int main()
 4 {
 5     int N;
 6     int a[1000];
 7     for(int i=0;i<=1000;i++){
 8         a[i]=0;
 9     }
10     //方法一：清零：判断是素数：1输出这个素数，2循环筛去其倍数，3将数组中的数清零
11     //疑点：数字从数组中清零后，之后的第一层循环因为数字N大小不会变，所以又会判断一遍
12     // 。  或是数组中的数字同为几个数的倍数，例如：6为2 和3 的倍数，去掉之后又去一遍？
13     
14     //方法二：循环遍历，将所有的素数的倍数在数组中的值（第几个素数即在a数组中的第几个位置）赋值为1，最后输出数组中为0的数
15     scanf("%d",&N);
16     for(int i=2;i<=N;i++)
17     {
18         if(a[i]==0)
19         {
20             for(int j=i*2;j<=N;j=j+i)
21                 a[j]=1;
22         }
23     }
24 
25     for(int i=2;i<=N;i++)
26     {
27         if(a[i]==0)
28             printf("%d\n",i);
29     }
30     return 0;
31 }

 

标签：筛法,int,样例,素数,数组,include
From： https://www.cnblogs.com/luoxiaoluo/p/16897331.html