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

JoeJoy

谢谢大佬！

找出10000000之内所有的素数

baige

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

永恒的蓝色梦想

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

永恒的蓝色梦想

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

鱼cpython学习者

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)

如果有错误，欢迎指正

永恒的蓝色梦想

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

复杂度爆表。

鱼cpython学习者

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

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

永恒的蓝色梦想

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

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

永恒的蓝色梦想

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

光 remove 效率就已经炸了

鱼cpython学习者

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

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

鱼cpython学习者

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

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

永恒的蓝色梦想

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

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

鱼cpython学习者

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

额，好吧