作者:
applebg (數學不及格)
2021-10-18 18:00:57我剛剛在想你的問題，我也玩python，show一下我自己寫的東西:
https://i.imgur.com/kYe62pG.png
據我所知，算質數只要檢查到n^1/2的floor就好(也就是n開根號再取地板)，
這是以前高中數學的內容了。其實你不用檢查到n的，這樣做你可以省下一半
要執行的敘述。
我把n這個數字給十萬，結果不到兩秒就算完了。我的電腦cpu是intel i7-4790
其實也很舊了。n給一百萬，那要花久一點，大概五到六秒鐘。
我想這就是演算法的魅力所在了，要去念數學！
作者:
Apache (阿帕契)
2021-10-18 18:05:00原來這id真的會寫代碼
作者:
bill1992 (我是魔法的蹤跡)
2021-10-18 18:54:00這寫法超慢
作者:
Hsins (翔)
2021-10-18 19:06:00了解一下 Sieve of Eratosthenes?
靠 原來是常識 我數學沒學過這個… 高職數學沒教啊 幹
作者:
brchiu (brchiu)
2021-10-18 19:23:00PRIMES is in P
作者:
pot1234 (鍋子)
2021-10-18 20:57:00跟2*3*7*…*23互質的話再做後面的test，不然慢到哭
作者:
HoloLens (GoogleGlass沒了ww)
2021-10-18 21:30:00n - sqrt(n) != n/2...
作者:
DrTech (竹科管理處網軍研發人員)
2021-10-18 21:35:00工程法：算一遍記起來，查表 。之後全部 O(1)，更快。
作者:
Hsins (翔)
2021-10-18 22:09:00然後就會被面試官噴了, 要不要什麼東西都做個表, 都 O(1)?
作者:
MyNion (Nion Lee)
2021-10-18 22:30:00樓上，那叫做動態規劃若時間瓶頸點早於空間，那確實用空間換時間是一個Approach另外有個折衷的算法叫布隆過濾器，也挺有趣的