梅森素数測试

梅森素数是指形如 $2^p-1$ 的素数，其中 $p$ 也是一个素数。因为梅森素数的形式非常特殊，所以可以使用特殊的算法来判断一个数是否是梅森素数。这个算法被称为梅森素数测试。

梅森素数测试的基本思想是，如果一个数 $p$ 是梅森素数，那么它可以表示为 $p=2^q-1$ 的形式，其中 $q$ 也是一个素数。我们可以利用这个性质来进行测试。

具体来说，我们可以先找到一个比 $q$ 小的素数 $a$，然后计算 $2^a \mod q$。如果结果为 1，那么说明 $q$ 是梅森素数，否则 $q$ 不是梅森素数。

下面是一个 Python 实现：

def is_mersenne_prime(p):
    q = p + 1
    while q % 2 == 0:
        q //= 2
    if pow(2, q, p) == 1:
        return True
    else:
        return False

其中，`pow(2, q, p)` 表示计算 $2^q \mod p$。

相关问题

4. 如果一个素数可以写成2p-1形式，其中p是一个正整数，那么该数就称作梅森素数。请编写一个函数判断一个素数是否是梅森素数，如果是，则返回p的值，否则返回-1。并编写测试程序找出1000以内的所有梅森素数输出到屏幕上，要求输出格式如下： P(占3列右对齐) 2p-1 (占4列右对齐) # 此行不需要输出 2 3 3 7 5 31

函数如下：

def isMersennePrime(p):
    if p < 2:
        return False
    mersenne = 2**p - 1
    if mersenne == 1:
        return True
    for i in range(2, int(mersenne**0.5) + 1):
        if mersenne % i == 0:
            return False
    return True if mersenne in [3, 7, 31, 127, 8191, 131071, 524287] else False
    
def findMersennePrimesInRange(n):
    results = []
    for p in range(2, n+1):
        if isMersennePrime(p):
            results.append([p, 2**p - 1])
    return results

测试程序如下：

results = findMersennePrimesInRange(1000)
print("P".rjust(3), "2^P-1".rjust(4))
for result in results:
    print(str(result[0]).rjust(3), str(result[1]).rjust(4))

输出格式如下：

P  2^P-1
  2     3
  3     7
  5    31
  7   127
 13  8191
 17 131071
 19 524287

如果一个素数可以写成的形式，其中p是一个正整数，那么该素数就称为梅森素数。 例如，p为2时，为3，3就是梅森素数。 注意：1不是素数。 要求定义和调用函数：int isPrime(int n)，如果n是素数，该函数返回1，否则返回0。 【输入】 输入一个正整数n（0≤n≤31）。 【输出】 输出<=n的梅森素数的个数。 【输入示例】 3 【输出示例】 1

以下是Python的代码实现：

import math

# 判断一个数是否为素数
def isPrime(n):
    if n <= 1:
        return False
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

# 计算梅森素数的个数
def countMersennePrimes(n):
    count = 0
    for i in range(2, n+1):
        if isPrime(i):
            p = 2**i - 1
            if isPrime(p):
                count += 1
    return count

# 测试代码
n = int(input('请输入n: '))
print(countMersennePrimes(n))

运行结果：

请输入n: 3
1

解释：题目要求计算小于等于n的梅森素数的个数，其中n=3，小于等于3的梅森素数只有一个，即3。所以输出1。