Python判断一个数是否为素数

2023-11-20 02:24| 来源: 网络整理| 查看: 265

前言

本文转自 Python学习日记 – 素数判断

扶木成枫 – 生命的绽放fmcf.ccfmcf.cc

对于一个数是否为素数，常规的方法就是 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() 嵌套，不必再多写一行代码来转换，其作用和 ="https://fmcf.cc/technology/654/#%E5%B0%86%E6%95%B4%E6%95%B0%E5%92%8C%E5%AD%97%E7%AC%A6%E4%B8%B2%E8%BD%AC%E6%8D%A2%E6%88%90%E6%B5%AE%E7%82%B9%E6%95%B0">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尾声

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

【本文地址】

公司简介

联系我们