題目連結:
給定一正整數 k (1 < k ≦ 1299709 (第 100000 個質數)。k = 0 代表輸入結束)。求出 k 所包含在的質數間隙(Prime Gap)之長度。
質數間隙為任意兩質數之間的間距。若 p 與 p + n 為兩相鄰質數,則此質數間隙長度即為 n 。如果 k 即是質數,則間隙長度算作 0 。
先將 1299709 以內的質數表建出來放進一個陣列裡。
接著每輸入進一個 k 值,先判斷 k 是否為質數。如果是質數就輸出「0」;反之,就再用二分搜搜尋 k 介於哪兩個相鄰質數之間,該對相鄰質數之差即是所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。