作者applebg (Malicious Racist)
看板Soft_Job
標題Re: [請益] 演算法的相關知識?
時間Mon Oct 18 18:00:57 2021
我剛剛在想你的問題，我也玩python，show一下我自己寫的東西:
https://i.imgur.com/kYe62pG.png
據我所知，算質數只要檢查到n^1/2的floor就好(也就是n開根號再取地板)，
這是以前高中數學的內容了。其實你不用檢查到n的，這樣做你可以省下一半
要執行的敘述。
我把n這個數字給十萬，結果不到兩秒就算完了。我的電腦cpu是intel i7-4790
其實也很舊了。n給一百萬，那要花久一點，大概五到六秒鐘。
我想這就是演算法的魅力所在了，要去念數學！
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.36.87.82 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Soft_Job/M.1634551260.A.9C3.html
1F：→ Apache: 原來這id真的會寫代碼 10/18 18:05
2F：推 s12358972: 看樓上才發現id 10/18 18:41
3F：推 bill1992: 這寫法超慢 10/18 18:54
4F：→ Hsins: 了解一下 Sieve of Eratosthenes? 10/18 19:06
5F：推 ke265379ke: 靠 原來是常識 我數學沒學過這個… 高職數學沒教啊 幹 10/18 19:12
6F：推 brchiu: PRIMES is in P 10/18 19:23
7F：→ gaowei16: 常識== 10/18 20:18
8F：推 pot1234: 跟2*3*7*…*23互質的話再做後面的test，不然慢到哭 10/18 20:57
9F：→ HoloLens: n - sqrt(n) != n/2... 10/18 21:30
10F：→ DrTech: 工程法：算一遍記起來，查表 。之後全部 O(1)，更快。 10/18 21:35
11F：→ Hsins: 然後就會被面試官噴了, 要不要什麼東西都做個表, 都 O(1)? 10/18 22:09
12F：推 MyNion: 樓上，那叫做動態規劃 10/18 22:30
13F：推 MyNion: 若時間瓶頸點早於空間，那確實用空間換時間是一個Approach 10/18 22:33
14F：→ MyNion: 另外有個折衷的算法叫布隆過濾器，也挺有趣的 10/18 22:35
15F：推 leoloveivy: 算過了就別算了 10/18 23:51
16F：推 viper9709: 推查表XDDD 10/19 00:35