1013 數素數
一、題目
令 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 和 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
四、題目分析
本題可以采取逐個判斷素數的方式獲得第i個素數，輸出給定范圍的素數，由于M、N的范圍有限，可以采取篩選法求素數，全域變數num[SIZE]元素的值為1表示其下標為素數，0表示其下標為合數（不包括0、1），陣列的大小定義為
1
0
6
10^6
106 ，
五、代碼
#include <bits/stdc++.h>
#define SIZE 1000000
using namespace std;
int num[SIZE];
int main()
{
int n; //讀入N
int m; //讀入M
int count = 0; //素數計數
int flag = 0; //控制格式
cin >> n >> m;
for (int i = 2; i < SIZE; i++)
num[i] = 1;
for (int i = 2; i < SIZE; i++)
if (num[i]) //i是質數
for (int j = i + i; j < SIZE; j += i)
num[j] = 0;
for (int i = 2; i < SIZE; i++)
if (num[i]) //i是質數
{
count++;
if (count < n)
continue;
else if (count > m)
break;
else
{
if (flag != 0)
if (flag % 10 == 0)
cout << '\n';
else
cout << ' ';
flag++;
cout << i;
}
}
return 0;
}
六、總結
-
篩選法求素數：
篩選法求素數適用于給定范圍的情況，首先從2開始，去掉所有2的倍數（自身除外），這里去掉的操作是把陣列元素置為0，然后把下一個元素（質數）的倍數去掉，直到剩余全為質數，
for (int i = 2; i < SIZE; i++) if (num[i]) //i是質數 for (int j = i + i; j < SIZE; j += i) num[j] = 0;
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/260293.html
標籤：其他
上一篇：Educational Codeforces Round 104 Div. 2 A~E
下一篇：順序表講解和實作