#22732: 求救 Python 大神，如何不 TLE
a007. 判斷質數
| From: [218.161.41.139] |
發表日期
:
2020-09-29 16:03
小的只會用 CPP 寫出建表和不建表來拿 AC (0.5s 和 1.6s)，有一點概念但解題報告#20495: 解法大全的一些數學理論實在理解不能。
有沒有大神能提點一下 Python 能拿 AC 的關鍵點在哪？
目前試過的方法
- I/O 用 stdin 和 stdout/print
- 建表用
(6k +- 1) - 建表只找小於 46341 的質數
- 試著用上述那篇提到的 Sieve of Eratosthenes 建表
- list 改用 deque
- 試過答案個別輸出和整包輸出
- 試著用 async def 改寫
#22733: Re:求救 Python 大神，如何不 TLE
a007. 判斷質數
| From: [61.223.37.233] |
發表日期
:
2020-09-29 16:12
網路上有質數判定法
https://chiendavid.blogspot.com/2020/03/zerojudge-a007.html
我放部落格很久了，可惜都 google 不到。
#22734: Re:求救 Python 大神，如何不 TLE
a007. 判斷質數
| From: [218.161.41.139] |
發表日期
:
2020-09-29 16:21
網路上有質數判定法
https://chiendavid.blogspot.com/2020/03/zerojudge-a007.html
我放部落格很久了，可惜都 google 不到。
看起來是米勒 - 拉賓算法 (Miller-Rabin Primilarity Test) 的實作？
我先試著理解看看，十分感謝
#22735: Re:求救 Python 大神，如何不 TLE
a007. 判斷質數
| From: [61.223.37.233] |
發表日期
:
2020-09-29 16:22
http://web.ntnu.edu.tw/~algo/Prime.html
#22736: Re:求救 Python 大神，如何不 TLE
a007. 判斷質數
| From: [218.161.41.139] |
發表日期
:
2020-09-29 17:16
大致是拿了 AC，但這段沒能搞懂，數學理論好難 Orz
def isPrime(n):
# 略
for sk in sprp:
# 略
for i in range(t-1):
x = pow(x, 2, n)
if (x == 1): return 0
if (x == n-1): break
if (x != n-1): return 0
return 1
需要理解這篇
http://web.ntnu.edu.tw/~algo/Prime.html
提到的 Strong Probable-prime Base，感謝提供範例和資料
ZeroJudge Forum