POJ 3006 Dirichlet's Theorem on Arithmetic Progressions

POJ 3006 http://poj.org/problem?id=3006

题目大意：找一个线性递增序列的第n个素数。

 

解题思路：直接搜嘛，线性复杂度O（n）

 

AC代码：

#include <iostream> #include <stdio.h> #include <cstring> #include <algorithm> #include <cmath> #include <stack> #include <stdlib.h> #include <set> //#define DEBUG using namespace std; typedef long long ll; int s,d,n; bool isPrime(int n) { if(n == 1|| n == 0) return 0; for(int i = 2;i * i <= n ; i++) { if(n % i == 0) return 0; } return 1; } int main() { while(cin >> s >> d >> n) { if(s==0 && d== 0 && n == 0) return 0; int ans = 0; for(int i = s ;;i+=d) { if(isPrime(i)) ans++; if(ans == n) { cout << i << endl; break; } } } return 0; }