ETH官方钱包

前往
大廳
主題

ZeroJudge - f803: 質數篩法練習 解題心得

Not In My Back Yard | 2021-05-04 00:00:04 | 巴幣 0 | 人氣 477

題目連結:


題目大意:
輸入第一列給定兩正整數 N 、 m (N < 10000000),代表質數表的上限以及 m 筆詢問。接著有 m 列輸入,每列給定一個質數。

請將正整數 1 ~ N 裡的所有質數放進一個列表裡形成一個質數表,並對於每個給定的質數,輸出其位於質數表中的第幾個位置(索引值從 1 開始)。



範例輸入:
1000 3
2
953
443


範例輸出:
1
162
86


解題思維:
先根據這題提及的方式(埃式篩法)建立出質數表。

因為輸入的 m 值其實不大,所以不需要額外建立一個位置列表,代表著每個質數所處的位置。因此對於每個輸入進的質數,利用二分搜尋法(Binary Search,見這題)去找到該質數在質數表中的何處,即可得到所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作