- 追加された行はこのように表示されます。
- 削除された行は
このように表示されます。
!!Problem A ディリクレの算術級数定理
こんばんは，選手諸君．
a と d が互いに素な正の整数ならば， a から始まり d ずつ増える等差数列 a, a + d, a + 2d, a + 3d, a + 4d, ... には無限個の素数が含まれる．このことはディリクレの算術級数定理として知られている．ガウス(Johann Carl Friedrich Gauss, 1777 - 1855)が予想していたことを， 1837年にディリクレ(Johann Peter Gustav Lejeune Dirichlet, 1805 - 1859)が証明した．
たとえば， 2から始まり3ずつ増える等差数列
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, ...
は，無限個の素数
2, 5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89, ...
を含む．
そこで君の使命だが，与えられた正整数 a と d と n に対して，この等差数列に含まれる n 番目の素数を求めるプログラムを書くことにある．
例によって，君もしくは君の仲間が疲れはて，あるいは混乱しても，当局はいっさい関知しないからそのつもりで．なお，この審判システムは3時間で自動的に停止する．成功を祈る．
!Input
入力はデータセットの並びである．データセットは， 1文字の空白で区切られた三つの正整数 a と d と n とからなる行である． a と d は互いに素である． a ≦ 9307 かつ d ≦ 346 かつ n ≦ 210 と仮定してよい．
入力の終わりは，1文字の空白で区切られた三つのゼロからなる行で示される．これはデータセットではない．
!Output
出力は入力データセットと同数の行で構成されなければならない．各行は一つの整数を含まなければならない．余計な文字を含めてはならない．
データセット a, d, n に対応する出力の整数は， a から始まり d ずつ増える等差数列に含まれる素数のうちで n 番目のものでなくてはならない．
なお，この入力条件の下で，結果は必ず 106 (百万)より小さいことがわかっている．
!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
!Output for the Sample Input
92809
6709
12037
103
93523
14503
2
899429
5107
412717
22699
25673
!!! 解答例
[[2006da1.c]]
素数を求める関数を用意しておくと良い。
*[[2006da1.c]] 素数を求める関数を使って、素数を数えていく。
*[[2006da1.cpp]] ↑のC++版
*[[2006da2.cpp]] 素数を配列を使って前もって求めておく