ETH官方钱包

切換
舊版
前往
大廳
主題

ZeroJudge - e539: 00967 - Circular　解題心得

Not In My Back Yard | 2019-11-21 23:47:30 | 巴幣 0 | 人氣 202
題目連結：
題目大意：
定義循環質數為：當一個整數把最左邊的位數移到最右邊，會產生一個新數字。而該新數字做一樣的操作也會產生另一個數字。重複以上步驟直到回到一開始的數字。而如果途中所有產生的數字皆是質數，則這些數字都是循環質數。

給定兩正整數 i 、 j （100 ≦ i ≦ j ≦ 1000000）。試問 i ～ j 之間有多少個循環質數？如果輸入只有一個「-1」，代表輸入結束。

沒有任何循環質數請輸出「No Circular Primes.」；只有一個的話，請輸出「1 Circular Prime.」；若有 n 個循環質數，請輸出「n Circular Primes.」。

範例輸入：
1000 1100
100 120
100 1000
-1
範例輸出：
No Circular Primes.
1 Circular Prime.
12 Circular Primes.
解題思維：
先建質數表。

然後建循環質數表。而循環質數的篩選法就是跑過所有可能的範圍（100 ～ 1000000）。

但是可以提早篩掉一些數字，像是 3 的倍數、包含 5 或 2 的數字等等。

再者，因為判斷一個數字是不是循環質數時，會跑過其他數字，所以其他跑到的數字會跟這個數字同樣是（不是）循環質數。所以下次遇到的時候不用再跑一次。

最後用類似像前綴和（Prefix Sum）的方式快速求得區間中的循環質數之數量。

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

作者相關創作

更多創作