題目内容:找第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())