UVA-1644 - Prime Gap

• UVa Online Judge 解題結果請於 Submit 後，參閱 uHunt。
• 如果你有任何建議與指教，歡迎於下方留言一起討論喔！
• 本題選為「20161220 大學程式能力檢定 CPE」題目。

題意概要

題目給定一個數字 $N$，請求出最接近這個數字 $N$ 的兩個質數間距有幾個數字，若該數字 $N$ 為質數，則輸出 0。

• 分析：本題為簡單的質數問題，因為題目已經給定數字的範圍，可以先建立一個表來記錄在題目範圍內的數字是否為質數。

Input

The input is a sequence of lines each of which contains a single positive integer. Each positive integer is greater than $1$ and less than or equal to the 100000th prime number, which is $1299709$. The end of the input is indicated by a line containing a single zero.

Output

The output should be composed of lines each of which contains a single non-negative integer. It is the length of the prime gap that contains the corresponding positive integer in the input if it is a composite number, or 0 otherwise. No other characters should occur in the output.

Sample Input

10
11
27
2
492170
0

Sample Output

4
0
6
0
114