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

applebg 發表於 2021/10/18 下午6:00:57

看板Soft_Job標題Re: [請益] 演算法的相關知識?作者

(Malicious Racist)時間Oct 18 18:00:57 2021推噓 9 推:9 噓:0 →:7

我剛剛在想你的問題，我也玩python，show一下我自己寫的東西:
https://i.imgur.com/kYe62pG.png

據我所知，算質數只要檢查到n^1/2的floor就好(也就是n開根號再取地板)，
這是以前高中數學的內容了。其實你不用檢查到n的，這樣做你可以省下一半
要執行的敘述。

我把n這個數字給十萬，結果不到兩秒就算完了。我的電腦cpu是intel i7-4790
其實也很舊了。n給一百萬，那要花久一點，大概五到六秒鐘。

我想這就是演算法的魅力所在了，要去念數學！

※ PTT 留言評論

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.36.87.82 (臺灣)

→

Apache10/18 18:05原來這id真的會寫代碼

推

s1235897210/18 18:41看樓上才發現id

推

bill199210/18 18:54這寫法超慢

→

Hsins10/18 19:06了解一下 Sieve of Eratosthenes?

推

ke265379ke10/18 19:12靠原來是常識我數學沒學過這個… 高職數學沒教啊幹

推

brchiu10/18 19:23PRIMES is in P

→

gaowei1610/18 20:18常識==

推

pot123410/18 20:57跟2*3*7*…*23互質的話再做後面的test，不然慢到哭

→

HoloLens10/18 21:30n - sqrt(n) != n/2...

→

DrTech10/18 21:35工程法：算一遍記起來，查表。之後全部 O(1)，更快。

→

Hsins10/18 22:09然後就會被面試官噴了, 要不要什麼東西都做個表, 都 O(1)?

推

MyNion10/18 22:30樓上，那叫做動態規劃

推

MyNion10/18 22:33若時間瓶頸點早於空間，那確實用空間換時間是一個Approach

→

MyNion10/18 22:35另外有個折衷的算法叫布隆過濾器，也挺有趣的

推