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