## PKU 3006 解题报告

### Description

If a and d are relatively prime positive integers, the arithmetic sequence beginning with a and increasing by d, i.e., a, a + d, a + 2d, a + 3d, a + 4d, ..., contains infinitely many prime numbers. This fact is known as Dirichlet's Theorem on Arithmetic Progressions, which had been conjectured by Johann Carl Friedrich Gauss (1777 - 1855) and was proved by Johann Peter Gustav Lejeune Dirichlet (1805 - 1859) in 1837.

For example, the arithmetic sequence beginning with 2 and increasing by 3, i.e.,

`2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92, 95, 98, ...,`

contains infinitely many prime numbers

`2, 5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89, ... .`

Your mission, should you decide to accept it, is to write a program to find the nth prime number in this arithmetic sequence for given positive integers a, d, and n.

### Input

The input is a sequence of datasets. A dataset is a line containing three positive integers a, d, and n separated by a space. a and d are relatively prime. You may assume a <= 9307, d <= 346, and n <= 210.

The end of the input is indicated by a line containing three zeros separated by a space. It is not a dataset.

### Output

The output should be composed of as many lines as the number of the input datasets. Each line should contain a single integer and should never contain extra characters.

The output integer corresponding to a dataset a, d, n should be the nth prime number among those contained in the arithmetic sequence beginning with a and increasing by d.

FYI, it is known that the result is always less than 106 (one million) under this input condition.

### Sample Input

```367 186 151 179 10 203 271 37 39 103 230 1 27 104 185 253 50 85 1 1 1 9075 337 210 307 24 79 331 221 177 259 170 40 269 58 102 0 0 0```

### Sample Output

```92809 6709 12037 103 93523 14503 2 899429 5107 412717 22699 25673```

### Source

Japan 2006 Domestic

```#include<stdio.h> #include<math.h>   int main() { int a,b,n; int i,j,k,count; while(scanf("%d%d%d",&a,&b,&n)!=EOF) { if(!a&&!b&&!n) return 0; count=0; for(i=a;i<=1000000&&count<n;i+=b) { k=sqrt(i)+1; for(j=2;j<=k;j++) { if(i%j==0) break; } if(i>1&&j>=k) count++; } printf("%dn",i-b); } return 0; }```

```#include<stdio.h> #include<string.h> bool isPrime[1000001]; int main() { int a,b,n; int i,j,k,count; memset(isPrime,true,sizeof(isPrime)); isPrime[1]=false; for(i=2;i<=1000000;i++) { if(isPrime[i]) for(j=i+i;j<=1000000;j+=i)isPrime[j]=false; } while(scanf("%d%d%d",&a,&b,&n)!=EOF) { if(!a&&!b&&!n) return 0; count=0; for(i=a;i<=1000000;i+=b) if(isPrime[i]) { count++; if(count==n) break; } printf("%dn",i); } return 0; }```
» 本博客采用署名 2.5 中国大陆许可协议进行许可，本文版权归作者所有，欢迎转载，但必须在明显位置给出原文连接。