Dirichlet's Theorem on Arithmetic Progressions - kyoupuro @ ウィキ

1141 : Dirichlet's Theorem on Arithmetic Progressions

問題文

解説

与えられた等差数列のn番目の素数を答える問題。
答えが100万よりも小さくなると問題文に書いてあるので、エラトステネスの篩を使って100万個分の配列をあらかじめ作っておけばOK。

プログラム

C

C++

#include <iostream>
using namespace std;
 
const int MAX = 1000000;
bool prime[MAX+1];
void func(int n) {
    if (prime[n]) return;
 
    for (int i = n*2; i <= MAX; i += n) {
        prime[i] = true;
    }
}
 
int main(){
    for (int i = 2; i*i <= MAX; i++) {
        func(i);
    }
    prime[1] = true;
 
    int a, d, n;
    while (cin >> a >> d >> n, a || d || n) {
        int cnt = 0;
        for (int i = a;; i += d) {
            if (!prime[i]) cnt++;
            if (cnt == n) {
                cout << i << endl;
                break;
            }
        }
    }
     
 
    return 0;
}

Java