1013 數素數 (20分)
令 P i P_i Pi 表示第 i i i 個素數。現任給兩個正整數 M ≤ N ≤ 1 0 4 M≤N≤10^4 M≤N≤104,請輸出 P M P_M PM 到 P N P_N PN 的所有素數。
輸入格式:
輸入在一行中給出 M M M 和 N N N,其間以空格分隔。
輸出格式:
輸出從 P M P_M PM 到 P N P_N 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
解題思路
- 利用埃氏篩打表素數
- 輸出時判斷是否已經輸出的數量是否是10的倍數
AC代碼
#include <iostream>
#include <string.h>
#include <vector>
using namespace std;
bool IsPrime[1000007];
vector<int> Prime;
void GetPrime()
{
for (int i = 2; i <= 1000007; ++i)
if (IsPrime[i])
{
Prime.push_back(i);
for (int j = 2 * i; j <= 1000007; j += i)
IsPrime[j] = false;
}
}
int main()
{
memset(IsPrime, true, sizeof(IsPrime));
IsPrime[0] = false;
IsPrime[1] = false;
int m, n;
cin >> m >> n;
GetPrime();
for (int i = m - 1, k = 0; i < n; ++i, ++k)
cout << Prime[i] << (i == n - 1 || k % 10 == 9 ? '\n' : ' ');
return 0;
}