Python学习日记 – 素数判断

前言

对于一个数是否为素数,常规的方法就是 2、5、7、11、13、17 来试验,可是这样的方法仅在 1000 以下的数有较高正确率,就在想,有没有一种绝对正确并且不使用 Python 其它模块的方法来判断素数,毕竟有了 Python 数学模块,素数的判断就变得很简单了,但是引入一个数学模块似乎会有些多余了。

常规算法

print("素数的概念是只可以被1和它本身整除的数字。\n欢迎来到这里,我们将在这里计算你所输入的数字是否为素数。")
while True:
    number = input("输入你的数字吧:")
    number = int(number)
    if number == 2:
        print("是素数")
    elif number == 3:
        print("是素数")
    elif number == 5:
        print("是素数")
    elif number == 7:
        print("是素数")
    elif number == 11:
        print("是素数")
    elif number == 17:
        print("是素数")
    elif number == 13:
        print("是素数")
    elif number == 19:
        print("是素数")
    else:
        if number % 2 == 0:
            print("\t此数可以被2整除,因此不是素数。")
        else:
            if number % 3 == 0:
                print("\t此数可以被3整除,因此不是素数。")
            else:
                if number % 5 == 0:
                    print("\t此数可以被5整除,因此不是素数。")
                else:
                    if number % 7 == 0:
                        print("\t此数可以被7整除,因此不是素数。")
                    else:
                        if number % 11 == 0:
                            print("\t此数可以被11整除,因此不是素数。")
                        else:
                            if number % 13 == 0:
                                print("\t此数可以被13整除,因此不是素数。")
                            else:
                                if number % 17 == 0:
                                    print("\t此数可以被17整除,因此不是素数。")
                                else:
                                    if number % 19 == 0:
                                        print("\t此数可以被19整除,因此不是素数。")
                                    else:
                                        print("是素数")

总共46行代码,可以在极短时间内,判断一个数是否为素数,但是这个算法,是不准确的!

如图,我们输入 5773 这个数字,它至少可以被 23、251、5773、1 这四个数整除,但是算法显示,是素数,因此这个算法是不准确的。

但是这个算法有个好处就是,可以很快的得出结论,是不需要消耗多少CPU算力的。

高阶算法

我们知道有一种绝对是素数的计算方法。

在判断一个数 n 是否是素数时,我们可以用从 1 到 n 的所有数,挨个去除 n 得到是否整除,如果整除的次数大于 2 就意味着除了 1 和 n 本身外,存在其它数可以整除它,就违背了素数的概念,意味着这个 n 就不是素数,反之是素数。

print("提示:最终结果的显示时间取决与CPU的算力和你输入的数大小\n建议输入一千万以下的数字,数字太大无法在短时间内得出结果")
x = int(input('输入一个数:'))
z = 0
for i in range(1,x+1):
    if x % i == 0:
        z = z+1
if z > 2:
    print("不是素数")
else:
    print("是素数")

这是一个高阶算法,利用Python本身的代码和函数完成的工作,它计算得到的结果是 100% 正确的,但是它有个唯一的缺点,因为使用的是穷举法,如果是十分巨大的数,我们无法在短时间内得到结果,需要消耗 CPU 的巨大算力去运算才行。

算法思维构建

常规算法

图上仅显示了一个简单的思维过程,其实是以此类推的,我们可以继续除7、11、13、17、23之类的。

高阶算法

这是一个近乎完美的方法

代码分析

前言

此次代码分析由于大量使用已经讲过的算法,因此仅分析两个内置函数。

使用 int() 进行数字转换

int() 函数在高阶算法中有使用,我们使用 int()input() 嵌套,不必再多写一行代码来转换,其作用和 float() 函数类似,但是它不会使得数字转化为浮点数,而是一个实实在在的数。

a = "2"
b = int(a)
print(b)
c = b+1
print(b)
print(c)

一个简单的实例,就可以看出它与 float() 函数的区别

运行结果是这样

2
2
3

它是不带小数点和小数点后面的数的。

使用 range() 来生成数

很简单的一个函数,可以到 Python range() 函数用法 | 菜鸟教程 具体学习。

我这里只举一个简单的例子

for a in range(1,10):
    print(a)

输出结果

1
2
3
4
5
6
7
8
9

尾声

素数算法的研究,是我开始算法研究迈出的第一步,以后会慢慢进步的!

此文由 Magneto 发布,本文采用《CC BY-NC-ND 4.0》协议,转载必须注明作者和本文链接。

评论

  1. Pad
    Windows Chrome
    5月前
    2022-7-25 15:54:15

    Hello!建议博主之后有空可以修改下这篇blog😀。

    • Magneto
      博主
      Pad
      Windows Edge
      5月前
      2022-7-25 19:45:40

      很好奇,这该怎么改

发送评论 编辑评论

Source: symbk.cn/technology/329
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
小恐龙
酷安
颜文字
Emoji
花!
上一篇
下一篇