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回目なのに一発で動かなかった。