洛谷题集——线性筛素数（一般筛选与线性筛选）

- 日理万妓 2023-02-16 00:47 10阅读 0赞

如题，给定一个范围 n，有 q 个询问，每次输出第 k 小的素数。

输入格式  
第一行包含两个正整数 n,q，分别表示查询的范围和查询的个数。  
接下来 q 行每行一个正整数 k，表示查询第 k 小的素数。  
输出格式  
输出 q 行，每行一个正整数表示答案。

输入输出样例  
输入 \#1 复制  
100 5  
1  
2  
3  
4  
5  
输出 \#1 复制  
2  
3  
5  
7  
11  
说明/提示  
【数据范围】  
对于100% 的数据，n = 108，1≤q≤106，保证查询的素数不大于 n。

--------------------

【普通筛——埃拉托斯特尼(Eratosthenes)筛法】  
时间复杂度O(n \* loglogn)

#include<cstdio>
    #define ll long long
    using namespace std;
    ll n, num=1;
    ll ss[100000010];
    int Q[1000010], q;
    bool judge[100000010]={ false};
    void init(void){ 
    	judge[1]=true;
    	
    	for(ll i=2; i<=n; i++){ 
    		if(judge[i]==false){ 
    			ss[num++]=i;
    			for(int j=2; j*i<=n; j++){ 
    				judge[i*j]=true;
    			}
    		}
    	}
    }
    
    int main(){ 
    	scanf("%lld%d", &n, &q);
    	init();
    	for(int i=0; i<q; i++){ 
    		scanf("%d", &Q[i]);
    	}
    	for(int i=0; i<q; i++){ 
    		printf("%lld", ss[Q[i]]);
    		if(i<q-1){ 
    			printf("\n");
    		}
    	}
    	
    	return 0;
    }

测试结果很感人，一个都没过……

--------------------

【线性筛——欧拉Euler筛】  
时间复杂度为O(n)  
原理：**最小质因数 × 最大因数（非自己） = 合数**  
[欧拉筛解析][Link 1]

#include<stdio.h>
    int n, num=1;
    int ss[100000010];
    int Q[1000010], q;
    bool judge[100000010]={ false};
    
    void init(void){ 
    	judge[1]=true;
    	
    	for(int i=2; i<=n; i++){  	
    		if(judge[i]==false){ 
    			ss[num++]=i;
    		}
    		for(int j=1; ss[j]*i<=n&&j<num; j++){ 
    			//ss[j]为 ss[j]*i 的最小质因数
    			judge[i*ss[j]]=true;	
    			//每个质数与每个因数组合
    			
    			//避免重复筛
    			//ss[j]为i的最小质因数
    			//若j++
    			//i*ss[j] 不符合 最小质因数*最大因数
    			if(i%ss[j]==0){ 		
    				break;				
    			}
    		}
    	}
    }
    
    int main(){ 
    	scanf("%d%d", &n, &q);
    	init();
    	for(int i=0; i<q; i++){ 
    		scanf("%d", &Q[i]);
    	}
    	for(int i=0; i<q; i++){ 
    		printf("%d", ss[Q[i]]);
    		if(i<q-1){ 
    			printf("\n");
    		}
    	}
    	
    	return 0;
    }

[Link 1]: https://www.luogu.com.cn/problem/solution/P3383