默尼森数

2016年09月17日

一、问题描述

找第n个默尼森数。P是素数且M也是素数,并且满足等式图片失效,则称M为默尼森数。

二、代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
# coding: utf-8
__author__ = 'zhongmingmao'

from math import sqrt
from math import log
from math import modf

# 缓存默尼森数
cacheMonisen = [3]
# 缓存素数
cachePrime = []

# 素数范围,搜索更多的素数
minNumber = 2
maxNumber = 100


def isPrime(x):
    '''判断是不是素数'''
    k = int(sqrt(x))
    for i in range(2, k + 1):
        if x % i == 0:
            return False
    return True


def addCachePrime():
    '''增加素数缓存'''
    for i in range(minNumber, maxNumber):
        if isPrime(i) and (i not in cachePrime):
            cachePrime.append(i)


def monisen(no):
    '''求解第N个默尼森数'''
    # 初始化素数缓存
    addCachePrime()
    if no <= len(cacheMonisen):
        return cacheMonisen[no - 1]
    beginIndex = int(cachePrime.index(cacheMonisen[-1]))
    for i in cachePrime[beginIndex + 1:-1]:
        # M和P均为素数
        if isPrime(i) and modf(log(i + 1, 2))[0] == 0:
            cacheMonisen.append(i)
        if no == len(cacheMonisen):
            break
    if no == len(cacheMonisen):
        return cacheMonisen[-1]
    else:
        # 素数范围不足,须增加素数,继续查找
        global minNumber, maxNumber
        minNumber, maxNumber = maxNumber, maxNumber * 2
        addCachePrime()
        return monisen(no)


print monisen(input())