AOJ 1141 Dirichlet's Theorem on Arithmetic Progressions
問題
Dirichlet's Theorem on Arithmetic Progressions | Aizu Online Judge
a+i*dという形の数字でn番目の素数を求めよ
方針
エラトステネスのふるいで素数リストを保持しておき、実際に求める
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, n) for(int i=0; i<(n); ++i) int p[1000001]; int main(void){ int a, d, n; p[0] = p[1] = -1; for(int i=2; i<=sqrt(1000000); ++i) { if(p[i] == 0) { for(int j=2; i*j<=1000000; ++j) { p[i*j] = -1; } } } while(cin >> a >> d >> n && a) { int cnt = 0; for(int i=a; ; i+=d) { if(p[i] == 0) cnt++; if(cnt==n) { cout << i << endl; break; } } } }
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1891470
反省
エラトステネスの篩書くのN回目なのに一発で動かなかった。