楼主:
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真的会写代码
作者:
bill1992 (我是魔法的踪迹)
2021-10-18 18:54:00这写法超慢
作者:
Hsins (翔)
2021-10-18 19:06:00了解一下 Sieve of Eratosthenes?
靠 原来是常识 我数学没学过这个… 高职数学没教啊 干
作者:
brchiu (brchiu)
2021-10-18 19:23:00PRIMES is in P
作者:
pot1234 (锅子)
2021-10-18 20:57:00跟2*3*7*…*23互质的话再做后面的test，不然慢到哭
作者:
HoloLens (GoogleGlass没了ww)
2021-10-18 21:30:00n - 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另外有个折衷的算法叫布隆过滤器，也挺有趣的