网站建设捌金手指专业1,宁波网站推广优化公司电话,wordpress阿里云cdn,网站安全防护情有独钟的素数
什么是素数
素数#xff08;Prime number#xff09;也称为质数#xff0c;是指在非0自然数中#xff0c;除了1与其本身之外不拥有其他因数的自然数。也就是说#xff0c;素数需要满足两个条件#xff1a;
大于1的整数#xff1b;只拥有1和其自身两个…情有独钟的素数
什么是素数
素数Prime number也称为质数是指在非0自然数中除了1与其本身之外不拥有其他因数的自然数。也就是说素数需要满足两个条件
大于1的整数只拥有1和其自身两个因数。
例子1
本文章的任务就是输出100以内的所有素数如2、3、5、7、11、13… 先理清一下思路 1需要有一个2~100的外循环还要有一个小于当前数的因子内循环 2需要有一个判断是否可整除的i语句整除就是余数为0。 求100以内的素数的思路如下图所示。
代码实现
实现代码如下 Python
# 100以内的素数算法
prime []
#从2开始遍厉到100
for i in range (2,101) :flag 1 #i是否力素数的标记# 因数应该是大于1小于自身的数for j in range (2, i):if i%j 0: #一旦取模余数为0flag 0 # 更改标记为0break # 直接跳出本循环if flag 1: # 标记为 1则为素数prime.append(i) # 添加到 prime 列表
print(100以内的素数,prime)Java ListInteger arr new ArrayList();int flag ;for(int i2;i101;i){flag 1;for (int j2;ji;j){if(i%j0){flag 0;break;}}if(flag1){arr.add(i);}}System.out.println(arr);输出结果如下 例子2 “优化素数计算从暴力求解到开方优化”
只要解决了问题就结束了吗这可不是学习的态度。《诗经》有云“如切如磋如琢如磨。”其斯之谓与我们可要精益求精啊。这段代码虽实现了我们的任务但它的时间复杂度太大100 以内的素数还可以如果是1000或10000呢 可是要怎样使时间复杂度变小呢只有两个地方可以下手——要么是外循环要么是内循环。我们知道任意数若等于两个非0自然数的乘积则这两个因子中至少有一个小于该数的二分之一。 当然我们还可以再缩小一下范围把“二分之一”缩减为“开方”这样就大大缩减了内循环的运行时间。思路如下图所示。
代码实现
实现代码如下 Python
# -*- coding: utf-8 -*-
import math#100以内的素数算法二
prime []
#从2开始遍历到 100
for i in range (2,101) :#因数应该是大于1小于自身的开方1for j in range(2,int(math.sqrt(i))1):#一旦取模余数为0if i%j 0:break #直接跳出本循环# 若余数均不0则为素数else:prime.append(i) # 添加到 prime 列表中print(100以内的全部素数,prime)Java ListInteger arr new ArrayList();int j;for(int i2;i101;i){for (j2;j(int)Math.sqrt(i)1;j){if(i%j0){break;}}if(j(int)Math.sqrt(i)1){arr.add(i);}}System.out.println(arr);注意例子二的内循环范围记得加1否则输出结果错误 输出结果如下 看我们只改了一个值便大大缩短了算法的运行时间这就是思维逻辑的重要性。只要逻辑捋顺了代码实现就很容易了。 例子3
观察结果发现5167-1611112,13-112, 1711819-118,23124…这些都是6的倍数那我们当不是可以利用6n-1和6n1两个公式便可以得到质数的排列了那么下一个质数必该是6×4135再下个质数就是6×5-129但是25并不是质数因此排列的规律还需要我们一步步地分析。 我们先不看2和3从5开始往后数所有的素数都分布在6nn≥1左右两侧即6n-1与6n1。那以6为间距的其他数又是如何分布的呢6n %606n2%206n3%306n4%206n5则又回到了6n-1一个循环结束了。 我们发现除去2和3以外所有的素数都是符合6n-1和6n1规律的但符合这两个公式的数字不一定就是素数因此这是一个充分非必要条件而不是充要条件。 据此我们可以进一步缩小因子范围思路如下图所示。
代码实现
实现代码如下 Python
# -*- coding: utf-8 -*-
import math# 100 以内的素数算法三
prime []
prime. extend([2, 3]) #已知2和3 是素数
# 从5开始遍历到 100
for i in range (5,101) :# 非素数时if i % 2 0 or i%3 0 :continue # 跳过后续操作直接进入下一循环# 因数应该是大于1小于自身的开方2以6为单位for j in range(6, int(math.sqrt(i))2,6):# 当可以整除6 的倍数时两侧的数字也为非素数if i%(j-1) 0 or i%(j1) 0:break # 直接跳出本循环# 若余数均不为O则为素数else:prime.append(i)
# 添加到 prime 列表中
print(100以内的全部素数,prime)Java
ListInteger arr new ArrayList();arr.add(2);arr.add(3);int j;for(int i5;i101;i){if (i%20 || i%30)continue;for (j6;j(int)Math.sqrt(i)2;j6){if(i%(j-1)0 || i%(j1)0){break;}}if(j(int)Math.sqrt(i)2){arr.add(i);}}System.out.println(arr);注意continue 和 break 非常好用不熟悉它们的用法的读者请务必掌握。 输出结果如下 “素数的广泛应用与未解决的数学难题”
这么一看果然“顺眼”多了虽然思路让人不好理解但多看几遍还是能理解的。一般来说实现相同功能的不同代码越简洁的就越晦涩运行时间越少的也越难懂。当然素数的检测算法远不止于此还有费马素性测试Fermat primality test、米勒-拉宾素性测试 Miller-Rabin primality test、Solovay-Strassen 测试、卢卡斯-菜默素性测试 Lucas-Lehmer primality test和埃拉托斯特尼筛法等。素数在自然数中的分布极其复架其被广泛应用到密码学中即在公钥中插入素数并进行编码以此达到提高破译难度的目的。 同时素数领域还存在许多数学家们一直无法解决的难题最著名的莫过于“哥德巴赫猜想”和“黎曼猜想”。哥德巴赫和黎曼在数学界都是举足轻重的人物。哥德巴赫猜想是“是否每个大于2的偶数都可写成两个素数之和”娶曼猜想是“素数出现的频率与黎曼 ζ \zeta ζ函数紧密相关。”这两个猜想虽然未能被完全验证但已经被广泛应用黎曼猜想甚至已经成为当今数学文献中一千多条数学命题的前提。
