由4开始检验每个数是否是质数

explore

彩蛋：我的寒假作业还有一大堆，明天开学，今天要创造奇迹了（悲，这是一个一个一个苦逼学牲啊




我屮艸芔茻，Discuz的代码排版是真乱

用的是最基本的算法：用数字来除所有已知的质数来判定
@xiaomeng 你瞅瞅？

（按Enter键下一个，输入'q'并Enter退出）

p.s：输出的不管看起来像是什么类型，为了加上用户友好的文字，都改成了string
p.p.s：每到整百数会输出一次截止目前的质数

[Python] 纯文本查看 复制代码

prime=[2,3]
num=4
NOT_PRIME=False

def is_prime(v):
    global NOT_PRIME#不声明全局变量会报错！！
    for n in prime:
        if v%n==0:
            NOT_PRIME=True
            print(str(v)+'不是质数',end='，下一个:')
            break#如果不加break，前一条“print”被打印几次可以代表这个数分解质因数时有几个不相等的质数因子
    if not NOT_PRIME:
        print(str(v)+'是质数',end='：')
        prime.append(v)


while input()!='q':
    is_prime(num)
    num+=1
    NOT_PRIME=False
    if num%100==0:
        print('\n\n'+str(prime))

liu12073

厉害！

xiaomeng

我有一只诡手，手尖缩回便无恙，手尖锁住便继续写代码，写不写，我定。

explore

liu12073 发表于 2023-2-3 17:27
厉害！

谬赞了

explore

xiaomeng 发表于 2023-2-3 22:34
我有一只诡手，手尖缩回便无恙，手尖锁住便继续写代码，写不写，我定。 ...

哦？我有一诡眼，闭上眼睛便无恙，眼睛睁开便想着摸鱼，摸不摸，我定

explore

xiaomeng 发表于 2023-2-3 22:34
我有一只诡手，手尖缩回便无恙，手尖锁住便继续写代码，写不写，我定。 ...

我发现这个算法的时间复杂度还挺难表示，

最坏应该是 O(这个数前面的质数的数量) （罢？）
最好应该是 O(1)----（偶数）

xiaomeng

explore 发表于 2023-2-3 23:25
我发现这个算法的时间复杂度还挺难表示，

最坏应该是 O(这个数前面的质数的数量) （罢？）

红蓝快选一个

xiaomeng

explore 发表于 2023-2-3 23:25
我发现这个算法的时间复杂度还挺难表示，

最坏应该是 O(这个数前面的质数的数量) （罢？）

代码整体上写的不错，没什么问题，继续加油

henry217

这里好像有问题


你只用2和3判断，如果我输入25，那么25既不是2的倍数也不是3的倍数，但它不是素数

explore

henry217 发表于 2023-2-4 11:18
这里好像有问题

如果检到了素数，它会加到素数列表里的（详见Line 14）
比如说循环到5，不能模2和3的结果为0，判为素数，append到末尾


p.s：列表“prime”其实可以就只有2一个元素，“num”从3开始，
3%2==1，这个判为素数也是可以的（就是有点不太严谨）