python高效的素数判断算法

高效素数判断算法

算法概述

此算法将其他博主对基本素数算法的一些改进进行了整合，其中主要整合了如下三条规则：

1.大于3的素数一定在6的倍数前一个或后一个（如素数37在36的后面）

2.要判断n是否为素数，只需要让n从2开始，依次除到根号n即可

3.在进行“让n从2开始，依次除到根号n”过程中，若n除以2的余数不为0，可以直接跳过[2, sqrt(n)]里面的所有偶数

博主语文素养不高，表达不是很准确，在后面会对这三条规则进行解释。

规则详解

1.大于3的素数一定在6的倍数前一个或后一个（如素数37在36的后面）

  • 数学证明：

任意一个整数n可以表示为n = 6a + b ( 0 <= b <= 5, a >= 0 )，接下来依次讲当n等于0到5的情况，以对此结论进行证明：

当n = 6a + 0 = 6a时，n有一个不为1及其本身的因数（素数判断条件）6，此类数不为素数

当n = 6a + 2 = 2( 3a + 1 )时，n有一个不为1及其本身的因数（素数判断条件）2，此类数不为素数

当n = 6a + 3 = 3( 2a + 1 )时，同上，有一因数3，此类数也不为素数

当n = 6a + 4 = 2( 3a + 2 )时，有一因数2， 此类数也不为素数

而当n = 6a + 1 或 n = 6a + 5时，不能绝对确定n是否为素数，需要考虑a的取值，显然此时的数值n就是分布在6的倍数前一个或后一个

总结：大于3的素数一定分布在6的倍数前后

  • 此规则可以直接对素数进行初步筛选，不符合此规则的数可直接判定为非素数，直接减少了2/3的运算量，效率提高肉眼可见
  • 注意小于等于3的素数(2, 3)需要另外判断

2.要判断n是否为素数，只需要让n从2开始，依次除到根号n即可

最基本的素数判断方法是：让n从2开始除，依次除到n - 1，如果每次除出来的结果余数皆不为0，那么此数n即为素数
实际上并不需要从除以[2, n - 1]区间的所有整数，只需除以[2, sqrt(n)]

3.在进行让n除以[2, sqrt(n)]区间内的所有整数操作时，如果2不是n的一个因数，那么之后可以不判断[2, sqrt(n)]区间的所有偶数

数学证明：当n/2除不尽时，n除以[2, sqrt(n)]区间内的所有偶数都除不尽

因此如果n不能将2除尽，那么之后的偶数一样除不尽，可以直接不除
如果将2除尽了，n就不是素数，直接排除
如果没有将2除尽，之后的计算量直接减半，肉眼可见的效率提升

算法时间复杂度复杂度

1.最基础的算法：也就是让n从2开始判断，一直到n-1

若遇到的数是素数时，此时需要进行n-2次判断
当遇到的不是素数时，要进行a（2<a<n-2)次判断
也就是说时间复杂度为n

2.改进后的算法：

根据规则二，判断素数只要从[2，sqrt(n)]即可，此时复杂度为sqrt(n)
根据规则3，无论如何都可以不判断2之后的偶数（当n大于2，当n除尽2时，n不为素数，之后不需要判断，如果n除不尽2时，之后的偶数不要判断）
假设n可以除尽2和不可以除尽2概率相等，那此时复杂度为sqrt(n)/4
根据规则一，只有1/3的数要进行判断，此时复杂度为sqrt(n)/12
也就是说时间复杂度为sqrt(n)/12

在计算过程中做出的假设以及计算过程并不那么严谨，此结果仅供参考

Python代码实现

def primeJudge(n):
 #先将数分为三类， 小于等于1，大于1小于5，和大于等于5
 #非整数统统不是素数
 if not isinstance(n, int): return False
 #小于1等于的都不是素数
 if n <= 1: return False
 #大于1小于5
 elif n == 2 or n == 3: return True
 #大于等于5
 elif n >= 5:
  #先判断是否在6的附近
  if n % 6 == 5 or n % 6 == 1:
   #再判断是否可以将2除尽
   #可以的话不是素数
   if n % 2 == 0: return False
   else:
    #不可除尽2，直接跳过所有偶数
    for i in range(3, int(sqrt(n) + 1), 2):
     if n % i == 0: return False
    #经过筛选即为素数
    return True
  #不在6的附近不是素数
  else: return False

以上就是python高效的素数判断算法的详细内容，更多关于python素数算法的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • Python实现粒子群算法的示例

    Python实现粒子群算法的示例

    粒子群算法是一种基于鸟类觅食开发出来的优化算法,它是从随机解出发,通过迭代寻找最优解,通过适应度来评价解的品质. PSO算法的搜索性能取决于其全局探索和局部细化的平衡,这在很大程度上依赖于算法的控制参数,包括粒子群初始化.惯性因子w.最大飞翔速度和加速常数与等. PSO算法具有以下优点: 不依赖于问题信息,采用实数求解,算法通用性强. 需要调整的参数少,原理简单,容易实现,这是PSO算法的最大优点. 协同搜索,同时利用个体局部信息和群体全局信息指导搜索. 收敛速度快, 算法对计算机内存和CPU要

  • python实现线性回归算法

    python实现线性回归算法

    本文用python实现线性回归算法,供大家参考,具体内容如下 # -*- coding: utf-8 -*- """ Created on Fri Oct 11 19:25:11 2019 """ from sklearn import datasets, linear_model # 引用 sklearn库,主要为了使用其中的线性回归模块 # 创建数据集,把数据写入到numpy数组 import numpy as np # 引用numpy库,主

  • Python查找算法之插补查找算法的实现

    Python查找算法之插补查找算法的实现

    一.插补查找算法 插补查找算法又称为插值查找,它是折半查找算法的改进版.插补查找是按照数据的分布,利用公式预测键值所在的位置,快速缩小键值所在序列的范围,慢慢逼近,直到查找到数据为止.根据描述来看,插值查找类似于平常查英文字典的方法.例如,在查一个以字母 D 开头的英文单词时,决不会用折半查找法.根据英文词典的查找顺序可知,D 开头的单词应该在字典较前的部分,因此可以从字典前部的某处开始查找.键值的索引计算,公式如下: middle=left+(target-data[left])/(data[

  • python 图像增强算法实现详解

    python 图像增强算法实现详解

    使用python编写了共六种图像增强算法: 1)基于直方图均衡化 2)基于拉普拉斯算子 3)基于对数变换 4)基于伽马变换 5)限制对比度自适应直方图均衡化:CLAHE 6)retinex-SSR 7)retinex-MSR其中,6和7属于同一种下的变化. 将每种方法编写成一个函数,封装,可以直接在主函数中调用. 采用同一幅图进行效果对比. 图像增强的效果为: 直方图均衡化:对比度较低的图像适合使用直方图均衡化方法来增强图像细节 拉普拉斯算子可以增强局部的图像对比度 log对数变换对于整体对比度

  • Python实现随机爬山算法

    Python实现随机爬山算法

    随机爬山是一种优化算法.它利用随机性作为搜索过程的一部分.这使得该算法适用于非线性目标函数,而其他局部搜索算法不能很好地运行.它也是一种局部搜索算法,这意味着它修改了单个解决方案并搜索搜索空间的相对局部区域,直到找到局部最优值为止.这意味着它适用于单峰优化问题或在应用全局优化算法后使用. 在本教程中,您将发现用于函数优化的爬山优化算法完成本教程后,您将知道: 爬山是用于功能优化的随机局部搜索算法. 如何在Python中从头开始实现爬山算法. 如何应用爬山算法并检查算法结果. 教程概述 本教程分为

  • python中K-means算法基础知识点

    能够学习和掌握编程,最好的学习方式,就是去掌握基本的使用技巧,再多的概念意义,总归都是为了使用服务的,K-means算法又叫K-均值算法,是非监督学习中的聚类算法.主要有三个元素,其中N是元素个数,x表示元素,c(j)表示第j簇的质心,下面就使用方式给大家简单介绍实例使用. K-Means算法进行聚类分析 km = KMeans(n_clusters = 3) km.fit(X) centers = km.cluster_centers_ print(centers) 三个簇的中心点坐标为: [

  • python入门之算法学习

    前言 参考学习书籍:<算法图解>[美]Aditya Bhargava,袁国忠(译)北京人民邮电出版社,2017 二分查找 binary_search 实现二分查找的python代码如下: def binary_search(list, item): low = 0 #最低位索引位置为0 high = len(list)- 1 #最高位索引位置为总长度-1 while low <= high: mid = (low + high)//2 #检查中间的元素,书上是一条斜杠,我试过加两条斜杠才

  • python实现ROA算子边缘检测算法

    python实现ROA算子边缘检测算法

    python实现ROA算子边缘检测算法的具体代码,供大家参考,具体内容如下 代码 import numpy as np import cv2 as cv def ROA(image_path, save_path, threshold): img = cv.imread(image_path) image = cv.cvtColor(img, cv.COLOR_RGB2GRAY) new = np.zeros((512, 512), dtype=np.float64) # 开辟存储空间 widt

  • Python查找算法之折半查找算法的实现

    Python查找算法之折半查找算法的实现

    一.折半查找算法 折半查找算法又称为二分查找算法,折半查找算法是将数据分割成两等份,首先用键值(要查找的数据)与中间值进行比较.如果键值小于中间值,可确定要查找的键值在前半段:如果键值大于中间值,可确定要查找的键值在后半段.然后对前半段(后半段)进行分割,将其分成两等份,再对比键值.如此循环比较.分割,直到找到数据或者确定数据不存在为止.折半查找的缺点是只适用于已经初步排序好的数列:优点是查找速度快. 生活中也有类似于折半查找的例子,例如,猜数字游戏.在游戏开始之前,首先会给出一定的数字范围(例

  • Python实现七大查找算法的示例代码

    Python实现七大查找算法的示例代码

    查找算法 -- 简介 查找(Searching)就是根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素.     查找表(Search Table):由同一类型的数据元素构成的集合     关键字(Key):数据元素中某个数据项的值,又称为键值     主键(Primary Key):可唯一的标识某个数据元素或记录的关键字 查找表按照操作方式可分为:         1.静态查找表(Static Search Table):只做查找操作的查找表.它的主要操作是:         ①

随机推荐