首页 > 代码库 > POJ 3006 Dirichlet's Theorem on Arithmetic Progressions 快筛质数
POJ 3006 Dirichlet's Theorem on Arithmetic Progressions 快筛质数
题目大意:给出一个等差数列,问这个等差数列的第n个素数是什么。
思路:这题主要考如何筛素数,线性筛。详见代码。
CODE:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 1000010 using namespace std; int prime[MAX],primes; bool notp[MAX]; int a,d,n; void Pretreatment() { notp[1] = true; for(int i = 2; i < MAX; ++i) { if(!notp[i]) prime[++primes] = i; for(int j = 1; j <= primes && i * prime[j] < MAX; ++j) { notp[i * prime[j]] = true; if(i * prime[j] == 0) break; } } } int main() { Pretreatment(); while(scanf("%d%d%d",&a,&d,&n),a + d + n) { for(int now = a;; now += d) { if(!notp[now]) --n; if(!n) { printf("%d\n",now); break; } } } return 0; }
POJ 3006 Dirichlet's Theorem on Arithmetic Progressions 快筛质数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。