へんてこのブログ

日々気づいたことや、最近やっていることを書いています

AOJ Volume11-1141

ICPC過去問
Problem A:ディリクレの算術級数定理
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1141&lang=jp

解法:全ての値を素数かチェックしていき、n番目の素数を出力する
check内のi*iが重要

#include<iostream>
#include<vector>


using namespace std;

bool check(int num) {
    if(num == 1) return false;
    if(num == 2) return true;
    
    for(int i=2;i*i <= num;i++) {
        if(num % i == 0) {
            return false;
        }
    }
    
    return true;
}

int main() {
    int a,d,n;
    
    while (cin >> a >> d >> n) {
        if(a == 0) break;
        
        int count = 0;
        int num = 0;
        int d_sum = a;
        while (count != n) {
            if(check(d_sum)) {
                count++;
                num = d_sum;
            }
            d_sum += d;
        }
        cout << num << endl;
    }
    
    
}