Dirichlet's Theorem on Arithmetic Progressions POJ - 3006 线性欧拉筛

  题意 给出a d n    给出数列 a,a+d,a+2d,a+3d......a+kd 问第n个数是几 保证答案不溢出

  直接线性筛模拟即可

 #include<cstdio>
#include<cstring>
using namespace std;
bool Is_Primes[];
int Primes[];
int A[];
int cnt;
void Prime(int n){
cnt=;
memset(Is_Primes,,sizeof(Is_Primes));
for(int i=;i<=n;i++){
if(!Is_Primes[i])
Primes[cnt++]=i;
for(int j=;j<cnt&&i*Primes[j]<n;j++){
Is_Primes[i*Primes[j]]=;
if(i%Primes[j]==)break;
}
} memset(Is_Primes,,sizeof(Is_Primes));
for(int i=;i<cnt;i++){
Is_Primes[Primes[i]]=;
} }
int main(){
int a,b,n;
Prime();
while(scanf("%d%d%d",&a,&b,&n)==&&a+b+n){ int ans=;
for(int i=;i<;i++){
A[i]=i*b +a;
// printf("%d %d\n",A[i],i);
if(Is_Primes[A[i]])ans++;
if(ans==n){
ans=A[i];
break;
}
}
printf("%d\n",ans); }
return ;
}
上一篇:Odoo(OpenERP)配置文件openerp-server.conf详解


下一篇:jQuery-1.9.1源码分析系列(十五) 动画处理——外篇