首页 > 代码库 > 【POJ3006】Dirichlet's Theorem on Arithmetic Progressions(素数筛法)
【POJ3006】Dirichlet's Theorem on Arithmetic Progressions(素数筛法)
简单的暴力筛法就可。
1 #include <iostream> 2 #include <cstring> 3 #include <cmath> 4 #include <cctype> 5 #include <cstdio> 6 #include <cmath> 7 #include <algorithm> 8 #include <numeric> 9 using namespace std;10 11 const int N = 1000005, M = 500005;12 bool is[N]; int prm[M];13 int getprm (int n) {14 int i, j, k = 0;15 int s, e = (int)(sqrt (0.0 + n) + 1);16 memset (is, 1, sizeof(is));17 prm[k ++] = 2; is[0] = is[1] = 0;18 for (i = 4; i < n; i += 2) is[i] = 0;19 for (i = 3; i < e; i += 2) {20 if (is[i]) {21 prm[k ++] = i;22 for (s = i * 2, j = i * i; j < n; j += s) {23 is[j] = 0;24 }25 }26 }27 for (; i < n; i += 2) {28 if (is[i]) prm[k ++] = i;29 }30 return k;31 }32 33 int main () {34 ios :: sync_with_stdio(false);35 //freopen("out.txt", "w", stdout);36 getprm(1000000);37 /*for (int i = 0 ; i < 78499; ++ i) {38 cout << i << " : " << prm[i] << endl;39 }*/40 long long a, d, n;41 long long cnt = 0, cur = 0;42 while (cin >> a >> d >> n) {43 if (a == 0 && d == 0 && n == 0) break;44 cnt = 0 ;45 while (1) {46 if (binary_search(prm, prm + 78499, a)) {47 cnt ++;48 if (cnt == n) break;49 }50 a += d;51 //cout << "step: " << cnt << " " << a << endl;52 }53 cout << a << endl;54 }55 return 0;56 }
【POJ3006】Dirichlet's Theorem on Arithmetic Progressions(素数筛法)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。