寻找第n个默尼森数

2017-11-05  本文已影响316人  极速魔法

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

#! /usr/bin/python
# -*- coding:utf-8 -*-
import math

def prime(num):
    if num <= 1:
        return False
    elif num == 2:
        return True
    else:
        for i in range(2, int(math.sqrt(num)) + 1):
            if num % i == 0:
                return False
        return True

#param no,return the no monisen number
def monisen(no):
    listPrime = [2]
    listMonisen = [3]
    #search the odd number,even number must not prime number
    i = 3
    #first monisen number
    if no == 1:
        return 3
    else:
        while True:

            if prime(i):
                temp = 2 ** i - 1
                if prime(temp):
                    listMonisen.append(2 ** i - 1)
                    if len(listMonisen) == no:
                        return listMonisen[no - 1]
                    else:
                        i += 2
                else:
                    i += 2
            else:
                i += 2


if __name__ == '__main__':

    print(monisen(2))

上一篇 下一篇

猜你喜欢

热点阅读