發表新討論
#22732: 求救 Python 大神，如何不 TLE


snakeneedy (蛇~Snake)

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


asnewchien@gmail.com (david)

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


snakeneedy (蛇~Snake)

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


asnewchien@gmail.com (david)

a007. 判斷質數 | From: [61.223.37.233] | 發表日期: 2020-09-29 16:22

http://web.ntnu.edu.tw/~algo/Prime.html

#22736: Re:求救 Python 大神，如何不 TLE


snakeneedy (蛇~Snake)

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