令 Pi 表示第 i 个素数。现任给两个正整数 M≤N≤104,请输出 PM 到 PN 的所有素数。
输入格式:
输入在一行中给出 M 和 N,其间以空格分隔。
输出格式:
输出从 PM 到 PN 的所有素数,每 10 个数字占 1 行,其间以空格分隔,但行末不得有多余空格。
输入样例:
5 27
输出样例:
11 13 17 19 23 29 31 37 41 43
47 53 59 61 67 71 73 79 83 89
97 101 103
思路
模板题。
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int m, n;
int prime[100010];
bool isprime[105010];
void ola()
{
memset(isprime, 1, sizeof(isprime));
int cnt = 0;
isprime[1] = 0;
for (int i = 2; i <= 105000; i++)
{
if (isprime[i])
prime[++cnt] = i;
for (int j = 1; j <= cnt && i * prime[j] <= 105000; j++)
{
isprime[i * prime[j]] = 0;
if (i % prime[j] == 0)
break;
}
}
}
int main()
{
cin >> m >> n;
ola();
for (int i = m; i <= n; i++)
cout << prime[i] << ((i - m) % 10 == 9 || i == n ? "\n" : " ");
return 0;
}