f803 - 質數篩法練習

🔗 前往 ZeroJudge 原題

題目描述

題目要求先建立小於 N 的質數表，然後針對 m 個詢問，輸出每個詢問的數字在質數表中的位置（索引）。

解題思路

本題使用埃拉托斯特尼篩法（Sieve of Eratosthenes）來建立質數表。首先，建立一個布林陣列 p，初始化所有元素為 0 (代表質數)，然後從 2 開始，將其所有倍數標記為非質數 (設為 1)。 建立質數表後，使用 map 資料結構 ans 儲存質數及其在表中的位置。對於每個詢問，直接從 map 中查找該質數的位置並輸出。

複雜度分析

• 時間複雜度: O(N log log N) + O(m)
  • 埃拉托斯特尼篩法的時間複雜度為 O(N log log N)。
  • 建立 map 的時間複雜度為 O(N)。
  • 查詢 map 的時間複雜度為 O(log N)，總共 m 次查詢，時間複雜度為 O(m log N)。
  • 總時間複雜度為 O(N log log N) + O(m log N)。如果 m 遠小於 N，可以近似為 O(N log log N)。
• 空間複雜度: O(N)
  • p 陣列佔用 O(N) 空間。
  • ans map 最多儲存 N-1 個質數，佔用 O(N) 空間。

程式碼

#include <iostream>
#include <cmath>
#include <map>
using namespace std;
int count,n,m;
bool p[10000000]={1,1};
map <int,int> ans;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n >> m;
	int sn=sqrt(n);
	for(int i=2;i<=sn;++i)
		for(int j=i+i;j<n;j+=i)
			p[j]=1;
	for(int i=2;i<n;++i)
		if(p[i]==0)ans[i]=++count;
	while(m--){
		cin >> n;
		cout << ans[n] << "\n";
 	}
}