鱼C论坛

 找回密码
 立即注册
查看: 6282|回复: 13

[技术交流] 18 - 数之吟唱:梅森素数

[复制链接]
发表于 2021-8-2 18:33:33 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 不二如是 于 2022-6-20 19:26 编辑

在线讲解:




                               
登录/注册后可看大图


梅森数(Mersenne Prime)指的是形如 2n-1 的正整数,其中指数 n 是素数,如果结果是一个是素数,则称其为梅森素数。

例如 22-1=3、23-1=7 都是梅森素数。

会不会觉得只要 n 是素数,结果也是呢?

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

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

66op000480oo8or56p1o.jpg

稍微扯远一些,1722 年,瑞士数学大师欧拉证明了231-1=2147483647 是一个素数,它共有 10 位数,成为当时世界上已知的最大素数。

2019 年名叫帕特里克·罗什的米国人利用“互联网梅森素数大搜索(GIMPS)”项目,成功发现第 51 个梅森素数 2^82589933-1。

该素数有 24862048 位,是迄今为止人类发现的最大素数。

如果用普通字号将它打印下来,其长度将超过100公里!

梅森素数历来都是数论研究中的一项重要内容,也是当今科学探索中的热点和难点问题。

nBnauM3X4UTNxgTOzATN0ETN1UTM1QDN5MjM5ADMwAjMwUzLwUzL3MzLt92YucmbvRWdo5Cd0FmLxE2L.jpg

1996 年初,美国数学家及程序设计师沃特曼编制了一个梅森素数计算程序,并把它放在网页上免费使用。

这一计算程序就是著名的 GIMPS 项目(全拼见下图),也是全球首个基于互联网的网格计算项目。

2021-08-02_19-33-34.jpg
官网:传送门

目前,全球有近 70 万人参与该项目,动用了超过 180 万核中央处理器联网来寻找梅森素数!

这在数学史上前所未有,在科学史上也极为罕见。

那么这一节课我们通过代码求出指数 n<22 的所有梅森素数。

我们要求 n<22 的所有梅森数,直觉告诉我们循环结构肯定要用到。

判断是否为素数的方式还是和上一讲一样,自定义一个函数:

  1. def prime(n):
  2.     m = math.sqrt(n)
  3.     i = 2
  4.     while i <= m:
  5.         if n % i == 0:
  6.             return 0
  7.         i += 1
  8.     return 1
复制代码

设变量 m 存储梅森数,整数 i 表示指数,其取值从 2~22。

i 每变化一次,都相应地计算出一个梅森数,存放在 m 中。

对每次计算得到的当前 m 值,都调用函数 prime() 进行判断,每次都将 m 的当前值作为实参传递给函 prime() 。

如果 n 为素数,则 prime() 函数返回值为 1,否则 prime() 函数返回值为 0 。

若 prime() 函数返回值为 1,则当前 m 为梅森素数,应该将其输出。

若 prime() 函数返回值为 0,则当前 m 不是梅森素数。

怎么判断梅森素数呢?

这是本讲的关键!

听上面的叙述,是不是觉得很难呢?

确实很难,一行代码搞定:

  1.   m = (2 ** i) - 1   
复制代码

哈哈哈哈哈哈,这节课可以下课了!

哈哈哈,还是要等下,跑一下代码吧:

2021-08-03_20-34-48.jpg

这节课虽然很简单,但是俗话说得好:

熟能生巧!

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

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

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

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


好啦,这节课就到这里,下课!

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

评分

参与人数 1荣誉 +5 贡献 +3 收起 理由
睦ちゃん她爹 + 5 + 3 加油

查看全部评分

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2021-8-2 19:28:34 | 显示全部楼层
666
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2021-11-5 17:10:52 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2021-11-9 17:33:38 | 显示全部楼层
  1. count = 0
  2. start = int(input('指定开始的数:'))
  3. stop = int(input('指定结束的数:'))
  4. for i in range(start,stop+1):
  5.     for n in range(2,i):
  6.         if  i % n == 0:
  7.             break
  8.     else:
  9.         m = (2**i - 1)
  10.         for j in range(2,m):
  11.             if m % j == 0:
  12.                 break
  13.         else:
  14.             print(f"{m}是梅森素数",end=' ')
  15.             count += 1
  16.             if count % 6 == 0:
  17.                 print( )

  18. print(f'\n{start}到{stop}之间共有{count}个梅森素数')
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-11-30 19:05:57 | 显示全部楼层
我的一个数循环好多次,烦躁
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-12-8 15:30:36 | 显示全部楼层
学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-2-20 03:20:57 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-2-21 23:27:52 | 显示全部楼层
学习中。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-4-17 10:46:01 | 显示全部楼层
123
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-4-17 12:38:04 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-5-9 15:02:24 | 显示全部楼层
# 题干
# 梅森数(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)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-8-26 14:16:38 | 显示全部楼层
懂了懂了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-11-14 20:47:54 | 显示全部楼层
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}')
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-6-6 21:46:29 | 显示全部楼层
sf
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 14:42

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表