判断质数的算法实现

这是和小朋友的一个数学游戏。比如，我们会在走路的时候，计算一个24点的题，或者在机场候机时，根据航班号，计算24点。

在更小一些的时候，做过0到100之间的质数的口头枚举。四年级暑假，在外面度假路上，我们一边走，一边玩互相给对方出数字，判断是否是质数的游戏。

只是一个游戏，并没有什么深远和特别的用意，或者说这只是打发时间的一个方式。

玩了小游戏之后，让小朋友试试用代码来实现一个判断素数的函数。下面是依次写的几个版本。

1


def is_prime(num):
    dog = int(input("随便输入一个数"))

    for i in range(2,9,1):
        if dog %i== 0:
            print(f" 这是一个质数{dog/i} ")
            return "🍩"
    else:
        print("这不是一个质数 ")

print(is_prime(9))

第一个版本，不完全正确，判断的除数没有穷尽，条件判断语句的关系没有写好。 这个版本是第一天的时候写的。

2


cat = int(input("输入1个从2开始的数"))
def is_prime (cat):
    if cat == 1:
        print("从2开始哦")
        return cat

    for i in range(2 , cat-1, 1):
        if cat % i ==0 :
            print("这不是一个质数")
            return cat, i
    if cat % i != 0:
        print("这是一个质数")

print(is_prime(cat))

第一个版本写完以后，当天没有马上修正和优化。第2个版本以及随后的版本，都是在第三天完成的。 第2个版本里面把条件判断语整理了一下，纠正了判断的除数的穷尽问题，也加上了用户输入1的时候的判断。

3


cat = int(input("输入1个从2开始的数"))
def is_prime (cat):
    if cat == 1:
        print("从2开始哦")
        return cat

    if cat % 2 == 0 :
        print("这不是一个质数")
        return cat, 2

    for i in range(3 , (cat-1)/2, 2):
        if cat % i ==0 :
            print("这不是一个质数")
            return cat, i
    if cat % i != 0:
        print("这是一个质数")

print(is_prime(cat))

在这个版本，我们讨论了程序执行的性能问题。 通过举例子，比如 19 ，需要判断的除数分别是哪几个，在纸上写出来以后，小朋友自主实现了先判断输入的是不是一个双数的问题。

然后关于除数要试到几为止的问题，小朋友自主提出了一个看法，只需要除到输入的参数的一半为止就可以，并解释了其中的逻辑。这个自主提出的想法并且加以实现的方法，让我有点汗颜。

4


cat = int(input("输入1个从2开始的数"))
def is_prime (cat):
    if cat == 1:
        print("从2开始哦")
        return cat

    if cat % 2 == 0 :
        print("这不是一个质数")
        return cat, 2

    import math
    tom=int(math.sqrt(cat))+1
    for i in range(3 , tom, 2):
        if cat % i ==0 :
            print("这不是一个质数")
            return cat, i
    if cat % i != 0:
        print("这是一个质数")

print(is_prime(cat))

因为小朋友还没有学习过平方和开方，我把这个知识点讲了一下，把除数判断推进到开方，并介绍了sqrt这个实现函数。

5


cat = int(input("输入1个从2开始的正整数"))
def is_prime (cat):
    # 判断输入的参数是否为质数
    # 输入 cat ，一个正整数
    # return 返回 (True/质数 ， 0) 或者 (False/非质数, 能被整除的数)
    import math
    if cat < 2:
        print("从2开始哦")
        return False, cat

    #如果能被2除掉就直接返回
    if cat % 2 == 0 :
        print("这不是一个质数")
        return False, 2

    #先加载数学模块再让 tom = cat 的开方
    tom=int(math.sqrt(cat))+1
    for i in range(3 , tom, 2):
        #判断是不是质数
        if cat % i ==0 :
            print("这不是一个质数")
            return False, i
    return True, 0

print(is_prime(cat))

这是在当天完成的版本，我们一起整理了代码，共同写了函数的注释。



tag: 教育 编程




权利声明： 未经许可，不得转载。