18 - 数之吟唱：梅森素数
本帖最后由 不二如是 于 2022-6-20 19:26 编辑在线讲解：
https://www.bilibili.com/video/BV1HT4y1K7DY
https://xxx.ilovefishc.com/forum/202105/31/204333obvdca8ankppcn9v.png.thumb.jpg
梅森数（Mersenne Prime）指的是形如 2n-1 的正整数，其中指数 n 是素数，如果结果是一个是素数，则称其为梅森素数。
例如 22-1＝3、23-1＝7 都是梅森素数。
会不会觉得只要 n 是素数，结果也是呢？
小师妹可以偷偷告诉你们，n 为 2，3，5，7 时，结果都是梅森素数哦，但是！
当 n 为 11 时，211-1=2047=23×89，可以拆分就不是梅森素数，所以上面的假设不成立。
稍微扯远一些，1722 年，瑞士数学大师欧拉证明了231-1＝2147483647 是一个素数，它共有 10 位数，成为当时世界上已知的最大素数。
2019 年名叫帕特里克·罗什的米国人利用“互联网梅森素数大搜索（GIMPS）”项目，成功发现第 51 个梅森素数 2^82589933-1。
该素数有 24862048 位，是迄今为止人类发现的最大素数。
如果用普通字号将它打印下来，其长度将超过100公里！
梅森素数历来都是数论研究中的一项重要内容，也是当今科学探索中的热点和难点问题。
1996 年初，美国数学家及程序设计师沃特曼编制了一个梅森素数计算程序，并把它放在网页上免费使用。
这一计算程序就是著名的 GIMPS 项目（全拼见下图），也是全球首个基于互联网的网格计算项目。
官网：传送门
目前，全球有近 70 万人参与该项目，动用了超过 180 万核中央处理器联网来寻找梅森素数！
这在数学史上前所未有，在科学史上也极为罕见。
那么这一节课我们通过代码求出指数 n<22 的所有梅森素数。
我们要求 n<22 的所有梅森数，直觉告诉我们循环结构肯定要用到。
判断是否为素数的方式还是和上一讲一样，自定义一个函数：
def prime(n):
m = math.sqrt(n)
i = 2
while i <= m:
if n % i == 0:
return 0
i += 1
return 1
设变量 m 存储梅森数，整数 i 表示指数，其取值从 2～22。
i 每变化一次，都相应地计算出一个梅森数，存放在 m 中。
对每次计算得到的当前 m 值，都调用函数 prime() 进行判断，每次都将 m 的当前值作为实参传递给函 prime() 。
如果 n 为素数，则 prime() 函数返回值为 1，否则 prime() 函数返回值为 0 。
若 prime() 函数返回值为 1，则当前 m 为梅森素数，应该将其输出。
若 prime() 函数返回值为 0，则当前 m 不是梅森素数。
怎么判断梅森素数呢？
这是本讲的关键！
听上面的叙述，是不是觉得很难呢？
确实很难，一行代码搞定：
m = (2 ** i) - 1
哈哈哈哈哈哈，这节课可以下课了！
哈哈哈，还是要等下，跑一下代码吧：
这节课虽然很简单，但是俗话说得好：
熟能生巧！
通过这几节课反复练习，我们应该熟练掌握自定义函数，循环嵌套，各种类型素数的求解。
还没掌握的，只有一个办法，反复敲代码，慢一点也没关系，真正理解了就好！
那什么才叫真正的理解了呢？
**** Hidden Message *****
好啦，这节课就到这里，下课！
源码： 666 {:5_90:} count = 0
start = int(input('指定开始的数：'))
stop = int(input('指定结束的数：'))
for i in range(start,stop+1):
for n in range(2,i):
ifi % n == 0:
break
else:
m = (2**i - 1)
for j in range(2,m):
if m % j == 0:
break
else:
print(f"{m}是梅森素数",end=' ')
count += 1
if count % 6 == 0:
print( )
print(f'\n{start}到{stop}之间共有{count}个梅森素数') 我的一个数循环好多次，烦躁 学习 {:5_102:} 学习中。 123 {:5_95:} # 题干
# 梅森数（Mersenne Prime）指的是形如 2^n-1 的正整数，其中指数 n 是素数，如果结果是一个是素数，则称其为梅森素数。
# 要求 n<22 的所有梅森数
def judge_primenumber(index):
storage = []
for i in range(2, index):
if index%i == 0:
storage.append(i)
break
if len(storage) == 0:
return True
else:
return False
count = 0
for index in range(2, 23):
number = 2 ** index - 1
if judge_primenumber(index) and judge_primenumber(number):
print('2^%d - 1 = %d' % (index, number))
count += 1
else:
continue
print('2 - 22 中共有 %d 个梅森素数' % count) 懂了懂了 import math
def prime(n):
x = math.sqrt(n)
i = 2
while i < x:
if n % i == 0:
return 0
i +=1
else:
return n
c = 0
for i in range(2,22):
m = 2**i-1
if prime(m) != 0:
c +=1
print(f'{c}={m}') sf
页:
[1]