Re: [請益] 演算法的相關知識? applebg PTT批踢踢實業坊

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

作者: 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真的會寫代碼

作者: s12358972 (Spice) 2021-10-18 18:41:00

看樓上才發現id

作者: bill1992 (我是魔法的蹤跡) 2021-10-18 18:54:00

這寫法超慢

作者: Hsins (翔) 2021-10-18 19:06:00

了解一下 Sieve of Eratosthenes?

作者: ke265379ke (山王澤北) 2021-10-18 19:12:00

靠原來是常識我數學沒學過這個… 高職數學沒教啊幹

作者: brchiu (brchiu) 2021-10-18 19:23:00

PRIMES is in P

作者: gaowei16 (啾啾人) 2021-10-18 20:18:00

常識==

作者: pot1234 (鍋子) 2021-10-18 20:57:00

跟2*3*7*…*23互質的話再做後面的test，不然慢到哭

作者: HoloLens (GoogleGlass沒了ww) 2021-10-18 21:30:00

n - 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另外有個折衷的算法叫布隆過濾器，也挺有趣的

作者: leoloveivy (cried) 2021-10-18 23:51:00

算過了就別算了

作者: viper9709 (阿達) 2021-10-19 00:35:00

推查表XDDD

繼續閱讀

[徵才] HyphenTechs徵Java Developer shooorio [請益] 外商/區塊鏈/新創 offer 請益morsha Re: [討論] 唐鳳分享如何成為蘋果電腦公司顧問的過程Hsins [徵才] Cymetrics 誠徵資安工程師keke0421 Re: [討論] 唐鳳分享如何成為蘋果電腦公司顧問的過程musashi0839 [討論] 唐鳳分享如何成為蘋果電腦公司顧問的過程musashi0839 [徵才] 動見科技 Android工程師(80K ~ 90K/3Y)yyz Re: [請益] 臉書面試繼續與否mochimacha [請益] 轉職需求技能godog3000 [討論] 視障按摩企業合作需要您的幫忙celebrate513