用Python实现素数相关算法并做注释说明
off999 2025-05-23 19:15 12 浏览 0 评论
大家好!我是幻化意识流。
当谈论素数相关算法时,以下是几个常见的算法,包括素数检测和生成素数序列。我将为你提供 Python 代码示例,并添加注释说明。
素数检测算法
方法一:试除法
def is_prime(num):
if num < 2:
return False
for i in range(2, int(num ** 0.5) + 1):
if num % i == 0:
return False
return True
注释说明:
is_prime 函数用于检测一个数是否为素数。
首先判断数是否小于 2,小于 2 的数都不是素数。
从 2 开始到平方根(取整)之间的数逐个试除,如果能整除,则不是素数,返回 False。
若循环结束仍然没有找到能整除的数,则说明是素数,返回 True。
方法二:Miller-Rabin 算法
import random
def is_prime(num, k=5):
if num < 2:
return False
if num in (2, 3):
return True
if num % 2 == 0:
return False
def check(a, s, d, n):
x = pow(a, d, n)
if x == 1 or x == n - 1:
return True
for _ in range(s - 1):
x = pow(x, 2, n)
if x == n - 1:
return True
return False
s, d = 0, num - 1
while d % 2 == 0:
s += 1
d //= 2
for _ in range(k):
a = random.randint(2, num - 2)
if not check(a, s, d, num):
return False
return True
注释说明:
is_prime 函数使用 Miller-Rabin 算法进行素数检测。
首先判断数是否小于 2,小于 2 的数都不是素数。
若数为 2 或 3,则为素数。
若数为偶数,则不是素数。
通过循环将数表示为 d * 2^s + 1 的形式。
对于给定的 k 值(默认为 5),选择 k 个随机数 a 进行检测。
check 函数用于执行 Miller-Rabin 算法的检测步骤,如果 a 的次方满足一定条件,则可能是素数。
若所有的随机数都通过检测,则返回 True,否则返回 False。
生成素数序列算法
方法一:埃拉托斯特尼筛法
def generate_primes(limit):
primes = [True] * (limit + 1)
primes[0] = primes[1] = False
p = 2
while p * p <= limit:
if primes[p]:
for i in range(p * p, limit + 1, p):
primes[i] = False
p += 1
prime_numbers = [num for num, is_prime in enumerate(primes) if is_prime]
return prime_numbers
注释说明:
generate_primes 函数用于生成小于等于给定限制值的素数序列。
创建一个布尔型列表 primes,初始化所有值为 True,用于标记素数。
将索引为 0 和 1 的位置设置为 False,因为它们不是素数。
从 2 开始循环到平方根小于等于限制值的数 p。
如果 p 是素数(primes[p] 为 True),则将 p 的倍数位置标记为 False。
循环结束后,所有为 True 的索引位置即为素数,将它们存储在列表 prime_numbers 中并返回。
这些是常见的素数相关算法的 Python 实现示例,你可以根据需要选择使用。
如果喜欢我的文章,麻烦动动您的大神之手帮我点个赞哦!本人在此深深的表示感谢!
相关推荐
- 推荐一款Python的GUI可视化工具(python 可视化工具)
-
在Python基础语法学习完成后,进一步开发应用界面时,就需要涉及到GUI了,GUI全称是图形用户界面(GraphicalUserInterface,又称图形用户接口),采用图形方式显示的计算机操...
- 教你用Python绘制谷歌浏览器的3种图标
-
前两天在浏览matplotlib官方网站时,笔者无意中看到一个挺有意思的图片,就是用matplotlib制作的火狐浏览器的logo,也就是下面这个东东(网页地址是https://matplotlib....
- 小白学Python笔记:第二章 Python安装
-
Windows操作系统的python安装:Python提供Windows、Linux/UNIX、macOS及其他操作系统的安装包版本,结合自己的使用情况,此处仅记录windows操作系统的python...
- Python程序开发之简单小程序实例(9)利用Canvas绘制图形和文字
-
Python程序开发之简单小程序实例(9)利用Canvas绘制图形和文字一、项目功能利用Tkinter组件中的Canvas绘制图形和文字。二、项目分析要在窗体中绘制图形和文字,需先导入Tkinter组...
- 一文吃透Python虚拟环境(python虚拟环境安装和配置)
-
摘要在Python开发中,虚拟环境是一种重要的工具,用于隔离不同项目的依赖关系和环境配置。本文将基于windows平台介绍四种常用的Python虚拟环境创建工具:venv、virtualenv、pip...
- 小白也可以玩的Python爬虫库,收藏一下
-
最近,微软开源了一个项目叫「playwright-python」,作为一个兴起项目,出现后受到了大家热烈的欢迎,那它到底是什么样的存在呢?今天为你介绍一下这个传说中的小白神器。Playwright是...
- python环境安装+配置教程(python安装后怎么配置环境变量)
-
安装python双击以下软件:弹出一下窗口需选择一些特定的选项默认选项不需要更改,点击next勾选以上选项,点击install进度条安装完毕即可。到以下界面,证明安装成功。接下来安装库文件返回电脑桌面...
- colorama,一个超好用的 Python 库!
-
大家好,今天为大家分享一个超好用的Python库-colorama。Github地址:https://github.com/tartley/coloramaPythoncolorama库是一...
- python制作仪表盘图(python绘制仪表盘)
-
今天教大家用pyecharts画仪表盘仪表盘(Gauge)是一种拟物化的图表,刻度表示度量,指针表示维度,指针角度表示数值。仪表盘图表就像汽车的速度表一样,有一个圆形的表盘及相应的刻度,有一个指针...
- 总结90条写Python程序的建议(python写作)
-
1.首先 建议1、理解Pythonic概念—-详见Python中的《Python之禅》 建议2、编写Pythonic代码 (1)避免不规范代码,比如只用大小写区分变量、使用容易...
- [oeasy]python0137_相加运算_python之禅_import_this_显式转化
-
变量类型相加运算回忆上次内容上次讲了是从键盘输入变量input函数可以有提示字符串需要有具体的变量接收输入的字符串输入单个变量没有问题但是输入两个变量之后一相加就非常离谱添加图片注释,不超过1...
- Python入门学习记录之一:变量(python中变量的规则)
-
写这个,主要是对自己学习python知识的一个总结,也是加深自己的印象。变量(英文:variable),也叫标识符。在python中,变量的命名规则有以下三点:>变量名只能包含字母、数字和下划线...
- 掌握Python的"魔法":特殊方法与属性完全指南
-
在Python的世界里,以双下划线开头和结尾的"魔法成员"(如__init__、__str__)是面向对象编程的核心。它们赋予开发者定制类行为的超能力,让自定义对象像内置类型一样优雅工...
- 11个Python技巧 不Pythonic 实用大于纯粹
-
虽然Python有一套强大的设计哲学(体现在“Python之禅”中),但总有一些情况需要我们“打破规则”来解决特定问题。这触及了Python哲学中一个非常核心的理念:“实用主义胜于纯粹主义”...
- Python 从入门到精通 第三课 诗意的Python之禅
-
导言:Python之禅,英文名是TheZenOfPython。最早由TimPeters在Python邮件列表中发表,它包含了影响Python编程语言设计的20条软件编写原则。它作为复活节彩蛋...
你 发表评论:
欢迎- 一周热门
- 最近发表
- 标签列表
-
- python计时 (73)
- python安装路径 (56)
- python类型转换 (93)
- python进度条 (67)
- python吧 (67)
- python字典遍历 (54)
- python的for循环 (65)
- python格式化字符串 (61)
- python静态方法 (57)
- python列表切片 (59)
- python面向对象编程 (60)
- python 代码加密 (65)
- python串口编程 (60)
- python读取文件夹下所有文件 (59)
- java调用python脚本 (56)
- python操作mysql数据库 (66)
- python获取列表的长度 (64)
- python接口 (63)
- python调用函数 (57)
- python多态 (60)
- python匿名函数 (59)
- python打印九九乘法表 (65)
- python赋值 (62)
- python异常 (69)
- python元祖 (57)