ICPC 国内予選2006A ディリクレの算術級数定理 AOJ 1141

エラトステネスやるだけ

ようやく競プロの感覚取り戻してきてやるだけ問題は秒でできるようになってきた。

#include <bits/stdc++.h>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
 
const ll MOD=1e9+7;
const ll INF=1e18;
 
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};

bool prime[1000005];

int main(){
    prime[1] = true;
    for(int i = 2;i < 1000000;i++){
        if(prime[i] == false){
            for(int j = 2;i*j < 1000000;j++){
                prime[i*j] = true;
            }
        }
    }
    while(true){
        int a,d,n;
        cin >> a >> d >> n;
        if(a + d + n == 0) break;
        int count = 0;
        for(int i = 0;a+d*i < 1000000;i++){
            if(prime[a+d*i] == false){
                count++;
                if(count == n){
                    cout << a+d*i << endl;
                    break;
                }
            }
        }
    }
}