AOJ_1141 POJ_3006 ディリクレの算術級数定理
問題(AOJ)
問題(POJ)
解法
エラトステネスの篩をつかうだけ。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; char prime[1000000]; int a, d, n; int main(){ memset(prime, sizeof(prime), 0); prime[1] = 1; for(int i = 2; i <= 1000; i++){ if(prime[i] == 0){ for(int j = 2 * i; j < 1000000; j += i) prime[j] = 1; } } while(scanf("%d %d %d", &a, &d, &n) && a){ int ans; for(int i = a; ; i += d){ if(prime[i] == 0){ n--; if(n == 0){ ans = i; break; } } } printf("%d\n", ans); } return 0; }