c668: 下一個質數
標籤 : math prime
通過比率 : 67% (6 人 / 9 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2018-07-22 13:57

內容

給您一個數字 n

請找出最接近 n 的質數 p

且 p > n


 本題無法以暴力 AC , 也無法利用建質數表來 AC , 請找出比較有效率的方法,

可參考

  米勒-拉賓質數判定法

  費馬小定理

  http://www.csie.ntnu.edu.tw/~u91029/Prime.html

  http://miller-rabin.appspot.com/


 

# python 的朋友,針對每行測資

s = sys.stdin.readline()
n = int(s)
k = n // 6

while(1):
    p = k * 6 + 1 ## 每 6 個數,測試 2 個,且末位是 5 不必測試。
    q = k * 6 + 5
    if(p > n and p%5!=0 and isPrime(p)):
        print(p)
        break
    if(q > n and q%5!=0 and isPrime(q)):
        print(q)
        break
    k += 1

 

輸入說明

每個測資點的第一行有三個數字   T  min  max

表示有 T 個待測數字,待測數字的最小值 min ,最大值 max。

所有的數字 n 小於 232

輸出說明
範例輸入
3 234 5543
234
2131
5543
範例輸出
239
2137
5557
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (14%): 0.5s , <1M
公開 測資點#1 (14%): 0.5s , <1M
公開 測資點#2 (14%): 0.5s , <1M
公開 測資點#3 (14%): 1.0s , <1M
公開 測資點#4 (14%): 1.5s , <10M
公開 測資點#5 (15%): 2.5s , <10M
公開 測資點#6 (15%): 3.0s , <10M
提示 :

感謝 icube 指導此題。

標籤:
math prime
出處:
[編輯:
asnewchien@gmai... (簡宏隆)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」