筛选N以内的素数

原创
2019/12/20 10:57
阅读数 21
点击上方蓝字,记得关注我们!


无一分可增不叫完美,无一分可减才是。--Antoine de Saint-Exupery

 筛选N以内的素数


1.题目描述

用简单素数筛选法求N以内的素数。

2.格式与样例

输入格式

N

输出格式

2N的素数

输入样例

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

3.参考答案1
 1#include<stdio.h>
2#include<math.h>
3int main()
4
{
5    int N,i,j,k;
6    scanf("%d",&N);
7    for(i=2;i<=N;i++)
8    {
9        k=(int)sqrt(i);        //这里对i取平方根再取整,sqrt需要有头文件#include<math.h>
10        for(j=2;j<=k;j++)
11        {
12            if(i%j==0)
13                break;
14         }
15         if(j>k)
16             printf("%d\n",i);
17         else
18             printf("");
19    }
20    return 0;
21}


3.参考答案2
 1#include<stdio.h>
2
3int fun(int n)
4
{
5   int i;
6   for(i=2;i*i<=n;i++)
7     if(n%i==0)return 0;
8   return 1;
9}
10int main()
11
{
12   int n,i;
13   scanf("%d",&n);
14   for(i=2;i<n;i++)
15      if(fun(i))printf("%d\n",i);
16   return 0
17}


END

“If you torture the data enough, it will confess”

                                           - - Ronald Coase


“阅读原文”我们一起进步



本文分享自微信公众号 - 电子荣耀(gh_05453579ed9d)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部