內容
// 注：本題為 【a058: Palindromic prime 迴文質數】 的加強版。
如果一個數字的位數超過一，且數字倒轉後仍然相同，也就是正讀反讀相同，則稱其為一個迴文數字。
如果一個質數又滿足迴文，則稱其為迴文質數，否則為普通質數。
給定兩個數字 L, R，請輸出在此範圍內(包含 L, R 本身)，所有普通質數與迴文質數的數量。
輸入說明
輸入僅一行，包含兩個數字 L, R，且所有測資滿足:
- R - L ≤ 5 * 106
- 1 ≤ L < R ≤ 1015
並且，部分測資滿足以下額外的限制:
- 30% 的測資滿足 1 ≤ L < R ≤ 1000。
- 40% 的測資滿足 1 ≤ L < R ≤ 107。
- 其餘的測資無其他限制。
輸出說明
輸出兩個整數 N, M，代表 普通質數 與 迴文質數 的數量。
迴文質數，是指位數大於1，且數字倒轉後仍然相同的質數。
如，131, 151, 191皆為迴文質數。
而，222, 2, 3, 4，皆非迴文質數，其中2, 3為普通質數。
一個普通質數，即一個非迴文的質數。
範例輸入
#1
100 200
範例輸出
#1
16 5
範例輸入
#2
99 101
範例輸出
#2
0 1
測資資訊：
記憶體限制：
512
MB
不公開 測資點#0 (10%): 1.0s , <1K
不公開 測資點#1 (10%): 1.0s , <1K
不公開 測資點#2 (10%): 1.0s , <1K
不公開 測資點#3 (10%): 1.0s , <1K
不公開 測資點#4 (10%): 1.0s , <1K
不公開 測資點#5 (10%): 1.0s , <1K
不公開 測資點#6 (10%): 1.0s , <1K
不公開 測資點#7 (10%): 1.5s , <1K
不公開 測資點#8 (10%): 2.0s , <1K
不公開 測資點#9 (10%): 2.5s , <1K
不公開 測資點#0 (10%): 1.0s , <1K
不公開 測資點#1 (10%): 1.0s , <1K
不公開 測資點#2 (10%): 1.0s , <1K
不公開 測資點#3 (10%): 1.0s , <1K
不公開 測資點#4 (10%): 1.0s , <1K
不公開 測資點#5 (10%): 1.0s , <1K
不公開 測資點#6 (10%): 1.0s , <1K
不公開 測資點#7 (10%): 1.5s , <1K
不公開 測資點#8 (10%): 2.0s , <1K
不公開 測資點#9 (10%): 2.5s , <1K
提示 ：
範例 2 的範圍中，僅有 101 一個迴文質數，沒有普通質數。
如果出現 RE(SIGKILL) 錯誤，代表迴圈太多次了。(這是系統限制我也沒辦法)
有沒有不用每個數字都花費 O(√n) 去檢查其質因數的方法呢?
標籤:
出處:
[管理者：
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 103 | a208 | 44 | 2024-08-26 20:46 |