实验4-2-9 梅森数 (20 分)

1. 题目摘自

https://pintia.cn/problem-sets/13/problems/454

2. 题目内容

形如 的素数称为梅森数（Mersenne Number）。例如 、 都是梅森数。1722年，双目失明的瑞士数学大师欧拉证明了 是一个素数，堪称当时世界上“已知最大素数”的一个记录。

输入格式：

输入在一行中给出正整数n（n<20）。

输出格式：

按从小到大的顺序输出所有不超过 的梅森数，每行一个。如果完全没有，则输出“None”。

输入样例：

6

输出样例：

3
7
31

3. 源码参考

#include <iostream>
#include <math.h>

using namespace std;

int prime(int n);

int main()
{
    int n;
    int k;

    cin >> n;

    for(int i = 1; i <= n; i++)
    {
        k = pow(2, i) - 1;
        if(prime(k))
        {
            cout << k << endl;
        }
    }

    return 0;
}

int prime(int n)
{
    int m = sqrt(n);

    if(n < 2)
    {
        return 0;
    }

    for(int i = 2; i <= m; i++)
    {
        if(n % i == 0)
        {
            return 0;
        }
    }

    return 1;
}