形如2 n −1的素数称为梅森数(mersenne number)。例如2 2 −1=3、2 3 −1=7都是梅森数。1722年,双目失明的瑞士数学大师欧拉证明了2 31 −1=2147483647是一个素数,堪称当时世界上“已知最大素数”的一个记录。 本题要求编写程序,对任一正整数n(n<20),输出所有不超过2 n −1的梅森数。 输入格式: 输入在一行中给出正整数n(n<20)。 输出格式: 按从小到大的顺序输出所有不超过2 n −1的梅森数,每行一个。如果完全没有,则
时间: 2023-05-31 15:18:27 浏览: 103
### 回答1:
输入格式:在一行中给出正整数n。
输出格式:按从小到大的顺序,每行输出一个不超过2^(n-1)的梅森素数。
解题思路:由梅森素数的定义可得:2^n-1是素数,n是正整数,则2^n-1才是梅森素数。然后判断2^n-1是否是素数。
详细实现请看代码:
### 回答2:
梅森数是指形如 $2^n-1$ 的素数,这种数很特殊,目前只发现了47个,并且其中许多大数仍未知是否素数。欧拉在18世纪证明了 $2^{31}-1$ 是一个素数,是当时人们所知的最大的素数,直到19世纪末,英国人盖尔发明了“筛子法”,才能得到更多的素数。
根据梅森数的定义,我们可以在 $2^n-1$ 的范围内枚举所有的数,然后利用素数判定法来判断是否是素数,如果是素数就输出。
具体的做法是,从2到 $2^n-1$ 枚举所有的数,如果当前的数是奇数,则继续进行判定,否则直接跳过,因为偶数不可能是素数。判定的方法是,从2到 $\sqrt{2^n-1}$ 枚举所有的数,如果有因子,则说明不是素数,直接退出,否则输出当前的数。
代码如下:
```python
import math
n = int(input())
for i in range(2, 2**n):
if i % 2 == 0:
continue
is_prime = True
for j in range(2, int(math.sqrt(i))+1):
if i % j == 0:
is_prime = False
break
if is_prime:
print(i)
if 2**n-2 < 2:
print("No Mersenne prime in range.")
```
需要注意的是,根据题目要求,如果没有任何一个梅森数,则需要输出"No Mersenne prime in range.",即需要特判一下,如果 $2^n-2<2$,即 $n<=1$,则直接输出提示信息。
### 回答3:
梅森数是形如 $2^n-1$ 的素数,其中 $n$ 是正整数。题目要求对于给定的正整数 $n$,输出所有不超过 $2^n-1$ 的梅森数。
思路:先用 Eratosthenes 筛法得到 $2^n-1$ 以内的所有素数,然后再判断每个素数是否为梅森数。判断方法是:若该素数 $p$ 能整除 $2^n-1$,则 $2^n-1$ 是梅森数。
程序如下:
```python
import math
def Eratosthenes(n):
is_prime = [True] * (n+1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(math.sqrt(n)) + 1):
if is_prime[i]:
for j in range(i*i, n+1, i):
is_prime[j] = False
return [i for i in range(n+1) if is_prime[i]]
n = int(input())
num = 2 ** n - 1
primes = Eratosthenes(num)
mersennes = [p for p in primes if (num % p == 0)]
for m in mersennes:
print(m)
if not mersennes:
print("None")
```
输入样例:
```
4
```
输出样例:
```
3
7
31
```