AOJ Volume11 1141: Dirichlet's Theorem on Arithmetic Progressions

エラトステネスの篩で素数を求めておく。

/****************************************************
*    2012/06/23                                        *
*    AOJ Volume11 1141                                *
*    Dirichlet's Theorem on Arithmetic Progressions    *
*    ディリクレの算術級数定理                        *
*    crane
*****************************************************/
#include<iostream>
#include<cmath>
using namespace std;

#define MAX_N 1000000

int field[MAX_N];

int main(){
    /*素数テーブル作成*/
    field[0] = 0; field[1] = 0;
    for(int i=2; i<MAX_N; i++)    field[i] = 1;//初期化
    for(int i=2; i<sqrt((double)MAX_N)+1; i++){
        if(field[i] == 1)
            for(int j=i*2; j<MAX_N; j+=i)
                field[j] = 0;
    }

    int a,d,n;    //a->aからはじめる,  dずる増える,　n番目目の素数
    while(cin >> a >> d >> n, (a||d||n)){
        int cnt = 0;
        while(1){
            if(field[a]==1) cnt++;
            if(cnt==n) break;
            a += d;
        }
        cout << a << endl;
    }
    return 0;
}