作者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/cn.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