线性筛法求素数(欧拉筛法)(求质数,O(n)时间复杂度)(外加求每个整数的最小质因子)(python)

本文主要是介绍线性筛法求素数(欧拉筛法)(求质数,O(n)时间复杂度)(外加求每个整数的最小质因子)(python),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前言:

python 中求质数的方法有好几种,这里就讲解时间复杂度最低的算法欧拉筛法,时间复杂度为O(n),这是数论中也是算法比赛中必须掌握的方法。

本篇博客还会额外讲解求每个整数的最小质因子,什么是质因子?顾名思义,就是是质数的因子,求这个有什么用呢?下篇博客X的因子链(数论,python)(算术基本定理)(欧拉筛法)会给大家讲解一道例题,在例题中讲解它的用法。

思路:

线性筛法的整体思路是(代码里有详细注释):

  1. 初始化一个长度为 n 的数组,再定义一个长度为n的bool类型数组,用来表示每个数是否为素数,为True表示不是素数
  2. 从2遍历到n,判断是否为素数(bool类型是否为False),若是素数,则将它的倍数标记为True

代码如下:

N = 10000
prime = [0] * N  # 存储所有的质数
cnt = 0  # 质数的个数
vis = [False] * N  # 标记数是否被筛过
for i in range(2, N):if not vis[i]:prime[cnt] = i  # 将当前数 i 记录为质数cnt += 1for j in range(cnt):if prime[j] * i >= N:  # 如果超出n 则无需后续操作直接退出循环breakvis[prime[j] * i] = True  # 标记 i*prime[j] 已经被筛过# 如果i是前面某个素数的倍数时, 说明i以后会由某个更大的数乘这个小素数筛去同理,# 之后的筛数也是没有必要的, 因此在这个时候, 就可以跳出循环了if i % prime[j] == 0:break

欧拉算法的特点就是每个数只会被自己的最小质因数筛过一次,所以由此保证了线性的时间复杂度。

求最小质因子只需在求素数的基础上加上两行代码即可

首先分析质数和非质数的最小质因子是什么。

  • 质数的最小质因子是它本身(因为1是因子但不是质数)
  • 非质数的最小质因子是什么呢?按正常思路分析不好得出结论,但在求素数的过程中有一步是对质数的倍数进行标记,通过这一步就可以判断出非质数的最小质因子是什么了。

代码如下:

N = 10000
prime = [0] * N  # 存储所有的质数
cnt = 0  # 质数的个数
vis = [False] * N  # 标记数是否被筛过
st = [0] * N  # 存储数的最小质因数for i in range(2, N):if not vis[i]:prime[cnt] = i  # 将当前数 i 记录为质数st[i] = i  # 当前数 i 的最小质因数为自身cnt += 1for j in range(cnt):if prime[j] * i >= N:  # 如果超出n 则无需后续操作直接退出循环breakst[prime[j] * i] = prime[j]  # 将 i*prime[j] 的最小质因数标记为 prime[j]vis[prime[j] * i] = True  # 标记 i*prime[j] 已经被筛过# 如果i是前面某个素数的倍数时, 说明i以后会由某个更大的数乘这个小素数筛去同理,# 之后的筛数也是没有必要的, 因此在这个时候, 就可以跳出循环了if i % prime[j] == 0:break

总结:

欧拉筛法是很多数论题型解法的“敲门砖”,下篇博客X的因子链(数论,python)(算术基本定理)(欧拉筛法)将讲解一道比较难的数论题,该题用到了本篇博客的欧拉筛法和最小质因子求法。

这篇关于线性筛法求素数(欧拉筛法)(求质数,O(n)时间复杂度)(外加求每个整数的最小质因子)(python)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/872367

相关文章

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)

一文带你搞懂Python中__init__.py到底是什么

《一文带你搞懂Python中__init__.py到底是什么》朋友们,今天我们来聊聊Python里一个低调却至关重要的文件——__init__.py,有些人可能听说过它是“包的标志”,也有人觉得它“没... 目录先搞懂 python 模块(module)Python 包(package)是啥?那么 __in

使用Python实现图像LBP特征提取的操作方法

《使用Python实现图像LBP特征提取的操作方法》LBP特征叫做局部二值模式,常用于纹理特征提取,并在纹理分类中具有较强的区分能力,本文给大家介绍了如何使用Python实现图像LBP特征提取的操作方... 目录一、LBP特征介绍二、LBP特征描述三、一些改进版本的LBP1.圆形LBP算子2.旋转不变的LB

Python中__init__方法使用的深度解析

《Python中__init__方法使用的深度解析》在Python的面向对象编程(OOP)体系中,__init__方法如同建造房屋时的奠基仪式——它定义了对象诞生时的初始状态,下面我们就来深入了解下_... 目录一、__init__的基因图谱二、初始化过程的魔法时刻继承链中的初始化顺序self参数的奥秘默认

Python实现特殊字符判断并去掉非字母和数字的特殊字符

《Python实现特殊字符判断并去掉非字母和数字的特殊字符》在Python中,可以通过多种方法来判断字符串中是否包含非字母、数字的特殊字符,并将这些特殊字符去掉,本文为大家整理了一些常用的,希望对大家... 目录1. 使用正则表达式判断字符串中是否包含特殊字符去掉字符串中的特殊字符2. 使用 str.isa

python中各种常见文件的读写操作与类型转换详细指南

《python中各种常见文件的读写操作与类型转换详细指南》这篇文章主要为大家详细介绍了python中各种常见文件(txt,xls,csv,sql,二进制文件)的读写操作与类型转换,感兴趣的小伙伴可以跟... 目录1.文件txt读写标准用法1.1写入文件1.2读取文件2. 二进制文件读取3. 大文件读取3.1

使用Python实现一个优雅的异步定时器

《使用Python实现一个优雅的异步定时器》在Python中实现定时器功能是一个常见需求,尤其是在需要周期性执行任务的场景下,本文给大家介绍了基于asyncio和threading模块,可扩展的异步定... 目录需求背景代码1. 单例事件循环的实现2. 事件循环的运行与关闭3. 定时器核心逻辑4. 启动与停

基于Python实现读取嵌套压缩包下文件的方法

《基于Python实现读取嵌套压缩包下文件的方法》工作中遇到的问题,需要用Python实现嵌套压缩包下文件读取,本文给大家介绍了详细的解决方法,并有相关的代码示例供大家参考,需要的朋友可以参考下... 目录思路完整代码代码优化思路打开外层zip压缩包并遍历文件:使用with zipfile.ZipFil

Python处理函数调用超时的四种方法

《Python处理函数调用超时的四种方法》在实际开发过程中,我们可能会遇到一些场景,需要对函数的执行时间进行限制,例如,当一个函数执行时间过长时,可能会导致程序卡顿、资源占用过高,因此,在某些情况下,... 目录前言func-timeout1. 安装 func-timeout2. 基本用法自定义进程subp

Python实现word文档内容智能提取以及合成

《Python实现word文档内容智能提取以及合成》这篇文章主要为大家详细介绍了如何使用Python实现从10个左右的docx文档中抽取内容,再调整语言风格后生成新的文档,感兴趣的小伙伴可以了解一下... 目录核心思路技术路径实现步骤阶段一:准备工作阶段二:内容提取 (python 脚本)阶段三:语言风格调