18 - 数之吟唱：梅森素数

鱼C-小师妹

在线讲解：

                               
登录/注册后可看大图

梅森数（Mersenne Prime）指的是形如 2ⁿ-1 的正整数，其中指数 n 是素数，如果结果是一个是素数，则称其为梅森素数。

例如 2²-1＝3、2³-1＝7 都是梅森素数。

会不会觉得只要 n 是素数，结果也是呢？

小师妹可以偷偷告诉你们，n 为 2，3，5，7 时，结果都是梅森素数哦，但是！

当 n 为 11 时，2¹¹-1=2047=23×89，可以拆分就不是梅森素数，所以上面的假设不成立。



稍微扯远一些，1722 年，瑞士数学大师欧拉证明了2³¹-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   

哈哈哈哈哈哈，这节课可以下课了！

哈哈哈，还是要等下，跑一下代码吧：



这节课虽然很简单，但是俗话说得好：

熟能生巧！

通过这几节课反复练习，我们应该熟练掌握自定义函数，循环嵌套，各种类型素数的求解。

还没掌握的，只有一个办法，反复敲代码，慢一点也没关系，真正理解了就好！

那什么才叫真正的理解了呢？

游客，如果您要查看本帖隐藏内容请回复

好啦，这节课就到这里，下课！

源码： 18.py.zip (750 Bytes, 下载次数: 11, 售价: 8 鱼币)

2021-8-3 20:56 上传

点击文件名下载附件

大马强

666

LyyLD

游刃鱿鱼

count = 0
start = int(input('指定开始的数：'))
stop = int(input('指定结束的数：'))
for i in range(start,stop+1):
    for n in range(2,i):
        if  i % 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}个梅森素数')

春风亭朝小树

我的一个数循环好多次，烦躁

aironeng

学习

张亚当

Asss-whom

学习中。

神里家的大小姐

123

hornwong

Hyjxsssss

# 题干
# 梅森数（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)

pu-007

懂了懂了

语与余

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}')

Alexiiis

sf