论坛 › Python交流 › 最低复杂度找出10000000之内的所有素数

JoeJoy 发表于 2020-8-13 13:17:20

最低复杂度找出10000000之内的所有素数

谢谢大佬！

找出10000000之内所有的素数

baige 发表于 2020-8-13 13:46:36

最低复杂度当然是自己算出来然后做成一张表。{:10_277:}

永恒的蓝色梦想 发表于 2020-8-13 13:52:53

欧拉筛法是个不错的选择。

永恒的蓝色梦想 发表于 2020-8-13 14:04:06

如果欧拉筛依然不能满足，那么来这里看看吧：https://www.zhihu.com/question/29580448

鱼cpython学习者 发表于 2020-8-15 21:31:56

list1 = list(range(3, 10000000, 2))
print(list1)
for item in list1:
        for item2 in range(2, 100000001):
                number = item * item2
                if number in list1:
                        list1.remove(number)
list1.insert(0, 2)
print(list1)

如果有错误，欢迎指正

永恒的蓝色梦想 发表于 2020-8-15 22:13:59

鱼cpython学习者 发表于 2020-8-15 21:31
如果有错误，欢迎指正

复杂度爆表。

鱼cpython学习者 发表于 2020-8-15 22:15:25

永恒的蓝色梦想 发表于 2020-8-15 22:13
复杂度爆表。

这不是按那个欧拉筛法做的吗，我寻思也没有多复杂啊

永恒的蓝色梦想 发表于 2020-8-15 22:20:01

鱼cpython学习者 发表于 2020-8-15 22:15
这不是按那个欧拉筛法做的吗，我寻思也没有多复杂啊

你这叫欧拉筛？埃氏筛都不如

永恒的蓝色梦想 发表于 2020-8-15 22:23:37

鱼cpython学习者 发表于 2020-8-15 22:15
这不是按那个欧拉筛法做的吗，我寻思也没有多复杂啊

光 remove 效率就已经炸了

鱼cpython学习者 发表于 2020-8-16 12:54:59

永恒的蓝色梦想 发表于 2020-8-15 22:20
你这叫欧拉筛？埃氏筛都不如

也不算欧拉筛，就看他的方法受到一点启发而已

鱼cpython学习者 发表于 2020-8-16 12:59:50

永恒的蓝色梦想 发表于 2020-8-15 22:23
光 remove 效率就已经炸了

可他要的是复杂度低，又不是效率低啊

永恒的蓝色梦想 发表于 2020-8-16 13:32:51

鱼cpython学习者 发表于 2020-8-16 12:59
可他要的是复杂度低，又不是效率低啊

复杂度是衡量效率的指标。

鱼cpython学习者 发表于 2020-8-16 16:31:50

永恒的蓝色梦想 发表于 2020-8-16 13:32
复杂度是衡量效率的指标。

额，好吧

查看完整版本: 最低复杂度找出10000000之内的所有素数