Re: [請益] 演算法的相關知識?

[applebg (Malicious Racist)]

我剛剛在想你的問題，我也玩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://www.ptt.cc/bbs/Soft_Job/M.1634551260.A.9C3.html
→ Apache: 原來這id真的會寫代碼
推 s12358972: 看樓上才發現id
推 bill1992: 這寫法超慢
→ Hsins: 了解一下 Sieve of Eratosthenes?
推 ke265379ke: 靠 原來是常識 我數學沒學過這個… 高職數學沒教啊 幹
推 brchiu: PRIMES is in P
→ gaowei16: 常識==
推 pot1234: 跟2*3*7*…*23互質的話再做後面的test，不然慢到哭
→ HoloLens: n - sqrt(n) != n/2...
→ DrTech: 工程法：算一遍記起來，查表 。之後全部 O(1)，更快。
→ Hsins: 然後就會被面試官噴了, 要不要什麼東西都做個表, 都 O(1)?
推 MyNion: 樓上，那叫做動態規劃
推 MyNion: 若時間瓶頸點早於空間，那確實用空間換時間是一個Approach
→ MyNion: 另外有個折衷的算法叫布隆過濾器，也挺有趣的
推 leoloveivy: 算過了就別算了
推 viper9709: 推查表XDDD