1013-数素数
leenickzh Lv4

表示第i个素数.现任给两个正整数M<=N<=,请输出的所有素数.

输入格式

输入在一行中给出MN,其间以空格分隔.

输出格式

输出从的所有素数,每10个数字占1行,其间以空格分隔,但行末不得有多余空格.

输入样例

1
5 27

输出样例

1
2
3
11 13 17 19 23 29 31 37 41 43
47 53 59 61 67 71 73 79 83 89
97 101 103

分析

  1. 埃氏筛法

算法从小到大枚举所有数,对每一个素数,筛去它的所有倍数,剩下的都是素数.

筛法代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
const int maxn = 101;  //表长
int prime[maxn],pNum = 0; //prime数组存放所有素数,pNum为素数个数
bool p[maxn] = {0}; //如果i为素数,则p[i]为false;否则,p[i]为true
void Find_Prime()
{
for(int i = 2;i < maxn;i++) //从2开始,i<maxn结束,不能写成i<=maxn
{
if(p[i] == false) //如果i是素数
{
prime[pNum++] = i; //把素数i存到prime数组中
for(int j = i+i;j<maxn;j+=i)
{
//筛去所有i的倍数,循环条件不能写成j<=maxn
p[j] = true;
}
}
}
}
  1. 1不是素数.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
using namespace std;

const int maxn = 1000001;
int prime[maxn], num = 0;
bool p[maxn] = {0};

void Find_Prime(int n)
{
for(int i =2;i < maxn;i++)
{
if(p[i]==false)
{
prime[num++] = i;
if(num > n) break;
for(int j = i+i;j < maxn;j+=i)
{
p[j] = true;
}
}
}
}

int main()
{
int M,N,count = 0;
cin>>M>>N;
Find_Prime(N);
for(int i = M;i<=N;i++)
{
cout<<prime[i-1];
count++;
if(count%10!=0&&i<N) cout<<" ";
else cout<<endl;
}
return 0;
}
  • Post title:1013-数素数
  • Post author:leenickzh
  • Create time:2021-05-18 22:47:30
  • Post link:https://nickk.cn/2021/05/18/1013-数素数/
  • Copyright Notice:All articles in this blog are licensed under BY-NC-SA unless stating additionally.
 Comments