寻找第n个默尼森数 python编程
问题描述:
寻找第n个默尼森数。
代码格式如下:
def prime(num):
...
def monisen(no):
… …
return xxx
print(monisen(int(input()))) # 此处输入由系统自动完成不需要自己输入,只要写这样一条语句即可(4分)
题目内容:
找第n个默尼森数。P是素数且M也是素数,并且满足等式M=2^P-1,则称M为默尼森数。例如,P=5,M=2^P-1=31,5和31都是素数,因此31是默尼森数。
输入格式:
按提示用input()函数输入
输出格式:
int类型
输入样例:
4
输出样例:
127
时间限制:1000ms内存限制:32000kb
python实现:
import math
def isPrime(num):
if num == 1:
return False
square_root = int(math.sqrt(num))
for i in range(2, square_root + 1):
if num % i == 0:
return False
return True
#获取下一个素数
def nextPrime(currentPrime):
flag = False
while flag == 0:
if currentPrime == 2:
currentPrime += 1
else:
currentPrime += 2
flag = isPrime(currentPrime)
return currentPrime
def monisen(no):
i = 1
p = 2
monisen_list = []
while i <= no:
m = int(math.pow(2, p) - 1)
if isPrime(m):
monisen_list.append(m)
i += 1
p = nextPrime(p)
return monisen_list[no - 1]
print(monisen(int(input())))
测试:
#print(monisen(int(input())))
if __name__ =='__main__':
for i in range(4):
print(monisen(int(input())))
print('*'*20)
结果: