筛选法找素数 数据范围很大 1 <= m <= n <= 1000000000 一开始不知道怎么做 查了一下 先筛选出40000内的素数 再依靠这些素数筛选题目要求的素数
#include <cstdio> #include <iostream> #include <cmath> #include <algorithm> #include <cstring> #define maxn 40000 using namespace std; int num_prime=0; bool vis[maxn]; int prime[4210]; bool is_prime[100010]; void init() { memset(vis, true, sizeof(vis)); vis[0] = vis[1] = 0; num_prime = 0; for(int i = 2; i < maxn; i++) if(vis[i]) { prime[++num_prime] = i; for(int j = 2*i; j < maxn; j += i) vis[j] = 0; } } int main() { init(); int t,flag = 0; scanf("%d",&t); while(t--) { if(flag) puts(""); else flag = 1; int _min,_max; scanf("%d%d",&_min,&_max); memset(is_prime, true, sizeof(is_prime)); for(int i = 1; i <= num_prime; i++) { int cc = _min/prime[i]; while(cc < 2 || cc*prime[i] < _min) cc++; for(int j = cc*prime[i]; j <= _max; j += prime[i]) { if(j >= _min && j <= _max) is_prime[j-_min]=0; } } if(_min == 1) is_prime[0] = 0; for(int i = 0; i <= _max-_min; i++) if(is_prime[i]) printf("%d\n",i+_min); } return 0; }
转载于:https://www.cnblogs.com/avema/p/3774283.html
