【POJ3006】Dirichlet's Theorem on Arithmetic Progressions(素数筛法)

简单的暴力筛法就可。

 #include <iostream>
#include <cstring>
#include <cmath>
#include <cctype>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <numeric>
using namespace std; const int N = , M = ;
bool is[N]; int prm[M];
int getprm (int n) {
int i, j, k = ;
int s, e = (int)(sqrt (0.0 + n) + );
memset (is, , sizeof(is));
prm[k ++] = ; is[] = is[] = ;
for (i = ; i < n; i += ) is[i] = ;
for (i = ; i < e; i += ) {
if (is[i]) {
prm[k ++] = i;
for (s = i * , j = i * i; j < n; j += s) {
is[j] = ;
}
}
}
for (; i < n; i += ) {
if (is[i]) prm[k ++] = i;
}
return k;
} int main () {
ios :: sync_with_stdio(false);
//freopen("out.txt", "w", stdout);
getprm();
/*for (int i = 0 ; i < 78499; ++ i) {
cout << i << " : " << prm[i] << endl;
}*/
long long a, d, n;
long long cnt = , cur = ;
while (cin >> a >> d >> n) {
if (a == && d == && n == ) break;
cnt = ;
while () {
if (binary_search(prm, prm + , a)) {
cnt ++;
if (cnt == n) break;
}
a += d;
//cout << "step: " << cnt << " " << a << endl;
}
cout << a << endl;
}
return ;
}
上一篇:Dirichlet's Theorem on Arithmetic Progressions


下一篇:构建ASP.NET MVC4+EF5+EasyUI+Unity2.x注入的后台管理系统(32)-swfupload多文件上传[附源码]