題目連結:
題目大意:
輸入第一列給定兩正整數 N 、 m (N < 10000000),代表質數表的上限以及 m 筆詢問。接著有 m 列輸入,每列給定一個質數。
請將正整數 1 ~ N 裡的所有質數放進一個列表裡形成一個質數表,並對於每個給定的質數,輸出其位於質數表中的第幾個位置(索引值從 1 開始)。
範例輸入:
1000 3
2
953
443
範例輸出:
1
162
86
解題思維:
因為輸入的 m 值其實不大,所以不需要額外建立一個位置列表,代表著每個質數所處的位置。因此對於每個輸入進的質數,利用二分搜尋法(Binary Search,見
這題)去找到該質數在質數表中的何處,即可得到所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。