【趣味学算法】14_梅森素数

大家好，欢迎来到IT知识分享网。

注： 本系列仅为个人学习笔记，学习内容为《算法小讲堂》（视频传送门），通俗易懂适合编程入门小白，需要具备python语言基础，本人小白，如内容有误感谢您的批评指正

梅森数（Mersenne Prime）指的是形如$2^n-1$的正整数，其中指数n是素数，如果结果是一个素数，则称其为梅森素数
例如$2^2-1=3$ ,$2^3-1=7$都是梅森素数，n 为 2，3，5，7 时，结果都是梅森素数，但是当 n 为 11 时，$2^{1}1-1=2047=23\times 89$，可以拆分就不是梅森素数,所以并不是所有指数为素数的情况都是梅森素数。

那么让我们用代码找出指数n<22的所有梅森素数该怎么实现呢？思路很简单！判断指数是不是素数然后在判断$2^n-1$是不是素数即可。

def prime(num): i = 2 while i<= math.sqrt(num): if num%i==0: return 0 i += 1 return 1 print('指数n<22的梅森素数为：') count = 0 for i in range(2,22): if prime(i): if prime(2i-1): print(2i-1) count += 1 print('22以内的梅森素数共有{}个'.format(count)) 

输出结果

指数n<22的梅森素数为： 3 7 31 127 8191   22以内的梅森素数共有7个 

在前面学习完了一些内容之后，素数大家一定都已经掌握了，让我们升级一下来看看著名的歌德巴赫猜想！

哥德巴赫猜想（Goldbach’s conjecture）是数论中存在最久的未解问：用现代的数学语言，哥德巴赫猜想可以陈述为：任一大于 2 的偶数，都可表示成两个素数之和。

这个猜想与当时欧洲数论学家讨论的整数分拆问题有一定联系。整数分拆问题是一类讨论“是否能将整数分拆为某些拥有特定性质的数的和”的问题。比如能否将所有整数都分拆为若干个完全平方数之和，或者若干个完全立方数的和等。而将一个给定的偶数分拆成两个素数之和，则被称之为此数的哥德巴赫分拆。

例如：

4 = 2 + 2 6 = 3 + 3 8 = 3 + 5 10 = 3 + 7 = 5 + 5 12 = 5 + 7 14 = 3 + 11 = 7 + 7 

那么让我们来验证验证歌德巴赫猜想对 2333 以内的正偶数都是成立的，即2333以内的不小于4的正偶数都能够分解为两个素数之和，实现思路当然也很简单啦就是将整数分解为两个正整数，再判断这两个正整数是否都为素数，输出最小的一组分解结果即可代码实现如下

def prime(num): i = 2 while i <= math.sqrt(num): if num%i==0: return 0 i += 1 return 1 if __name__=='__main__': while True: num = int(input('请输入一个不小于4的正偶数，退出输入0：')) if num==0: print('已退出！') break elif num%2!=0 or num < 4: print('输入不合法请重新输入！') print() continue i = 2 while i <= num//2: if prime(i)and prime(num-i): print('分解结果：{}\t{}'.format(i,num-i)) print() break i += 1 

输出结果：

请输入一个不小于4的正偶数，退出输入0：2 输入不合法请重新输入！ 请输入一个不小于4的正偶数，退出输入0：9 输入不合法请重新输入！ 请输入一个不小于4的正偶数，退出输入0：18 分解结果：5 13 请输入一个不小于4的正偶数，退出输入0：300 分解结果：7 293 请输入一个不小于4的正偶数，退出输入0：0 已退出！