Python - 寻找第n个默尼森数

Python - 寻找第n个默尼森数

题目内容：找第n个默尼森数。P是素数且M也是素数，并且满足等式M=2**P-1，则称M为默尼森数。例如，P=5，M=2**P-1=31，5和31都是素数，因此31是默尼森数。

输入格式:用input()函数输入，注意如果Python 3中此函数的返回类型。

输出格式：int类型

输入样例：4

输出样例：127

时间限制：500ms内存限制：32000kb

思路：素数打表 + 枚举

AC代码：

# -*- coding:utf-8 -*- import mathdef prime(n): # 判断是否为素数 if n < 2: return False for i in range(2, int(math.sqrt(n)) + 1): if n % i == 0: return False return Truedef monisen(maxn): '''''' # 素数打表 prime_dic = {} prime_list = [] n = 10000 for i in range(2, n + 1): prime_dic[i] = 1 for i in range(2, int(n ** .5) + 1): for j in range(i * i, n + 1, i): if prime_dic[i] == 1: prime_dic[j] = 0 for k, v in prime_dic.items(): if v == 1: prime_list.append(k) '''''' for i in prime_list: # 枚举2**prime-1到第maxn个 mon = 2 ** i - 1 if prime(mon): maxn = maxn - 1 if maxn <= 0: return mon print monisen(input())

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。