prithivMLmods/Coder-Stat

1 2<h1><font color="#000">Problem A:</font> Dirichlet's Theorem on Arithmetic Progressions</h1>3 4<p>5Good evening, contestants.6</p>7 8<p>9If <i>a</i> and <i>d</i> are relatively prime positive integers,10the arithmetic sequence beginning with <i>a</i>11and increasing by <i>d</i>, i.e.,12<i>a</i>,13<i>a</i> + <i>d</i>,14<i>a</i> + 2<i>d</i>,15<i>a</i> + 3<i>d</i>,16<i>a</i> + 4<i>d</i>,17...,18contains infinitely many prime numbers.19This fact is known as Dirichlet's Theorem on Arithmetic Progressions,20which had been conjectured by Johann Carl Friedrich Gauss (1777 - 1855)21and was proved by Johann Peter Gustav Lejeune Dirichlet (1805 - 1859)22in 1837.23</p>24 25 26 27<p>28For example,29the arithmetic sequence beginning with 2 and increasing by 3,30i.e.,31</p>32 33<blockquote>342,355,368,3711,3814,3917,4020,4123,4226,4329,4432,4535,4638,4741,4844,4947,5050,5153,5256,5359,5462,5565,5668,5771,5874,5977,6080,6183,6286,6389,6492,6595,6698,67...68,69</blockquote>70 71<p>72contains infinitely many prime numbers73</a></p>74<!-- end en only -->75<blockquote>762,775,7811,7917,8023,8129,8241,8347,8453,8559,8671,8783,8889,89...90<!-- begin en only -->91.92<!-- end en only -->93</blockquote>94 95<!-- begin en only -->96<p>97Your mission, should you decide to accept it,98is to write a program to find99the <i>n</i>th prime number in this arithmetic sequence100for given positive integers <i>a</i>, <i>d</i>, and <i>n</i>.101</p>102<!-- end en only -->103 104<!-- begin en only -->105<p>106As always, should you or any of your team be tired or confused,107the secretary disavow any knowledge of your actions.108This judge system will self-terminate in three hours.109Good luck!110</p>111<!-- end en only -->112 113 114<h2>Input</h2>115 116<!-- begin en only -->117<p>118The input is a sequence of datasets.119A dataset is a line containing three positive integers120<i>a</i>, <i>d</i>, and <i>n</i> separated by a space.121<i>a</i> and <i>d</i> are relatively prime.122You may assume <i>a</i> &lt;= 9307, <i>d</i> &lt;= 346,123and <i>n</i> &lt;= 210.124</p>125<!-- end en only -->126 127<!-- begin en only -->128<p>129The end of the input is indicated by a line130containing three zeros separated by a space.131It is not a dataset.132</p>133<!-- end en only -->134 135<!-- begin en only -->136<p>137</p>138<!-- end en only -->139 140 141 142<h2>Output</h2>143 144<!-- begin en only -->145<p>146The output should be composed of147as many lines as the number of the input datasets.148Each line should contain a single integer149and should never contain extra characters.150</p>151<!-- end en only -->152 153<!-- begin en only -->154<p>155The output integer corresponding to156a dataset <i>a</i>, <i>d</i>, <i>n</i> should be157the <i>n</i>th 158prime number among those contained159in the arithmetic sequence beginning with <i>a</i>160and increasing by <i>d</i>.161</p>162<!-- end en only -->163 164<!-- begin en only -->165<p>166FYI, it is known that the result is always less than16710<sup>6</sup> (one million)168under this input condition.169</p>170<!-- end en only -->171 172 173<h2>Sample Input</h2>174 175<pre>176367 186 151177179 10 203178271 37 39179103 230 118027 104 185181253 50 851821 1 11839075 337 210184307 24 79185331 221 177186259 170 40187269 58 1021880 0 0189</pre>190 191 192<h2>Output for the Sample Input</h2>193 194<pre>195928091966709197120371981031999352320014503201220289942920351072044127172052269920625673207</pre>208