题目内容:找第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
思路:素数打表 + 枚举
# -*- coding:utf-8 -*-
import math
def prime(n): # 判断是否为素数
if n < 2:
return False
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
return False
return True
def 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())