UVA1180

Hywel · 2021-10-11 21:46:36 · 题解

大数学家欧拉推导得出

如果 p 是质数，且 2^p-1 也是质数，那么 (2^p-1)* 2^{p-1} 便是一个完全数。

例如 p=2，是一个质数，2^p-1=3 也是质数，(2^p-1) * 2^{p-1} =3 * 2=6，是完全数。

例如 p=3，是一个质数，2^p-1=7 也是质数，(2^p-1) * 2^{p-1}=7 * 4=28，是完全数。

例如 p=5，是一个质数，2^p-1=31 也是质数，(2^p-1) * 2^{p-1}=31 * 16=496，是完全数。

但是 2^p-1 什么条件下才是质数呢?事实上，当 2^p-1 是质数的时候，称其为梅森素数。到2013年2月6日为止，人类只发现了 48 个梅森素数，较小的有 3、7、31、127 等。

所以说只要写一个质数判断程序，判断 p 和 2^p-1 是否是质数即可。

#include <iostream>
using namespace std;

int main()
{
  int n, i;
  bool isPrime = true;

  cin >> n;

  for(i = 2; i <= n / 2; ++i)
  {
      if(n % i == 0)
      {
          isPrime = false;
          break;
      }
  }
  if (isPrime)//是素数
      cout << "???";
  else//不是素数
      cout << "...";

  return 0;
}

或者写一个线性筛

#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T &x)
{
    x = 0 ; int w = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch=getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
    x *= w;
    FUCKER:;
}
template<typename T>inline void write(T x)
{
    if(x == 0){putchar('0');return ;}
    if(x < 0){putchar('-');x = -x;}
    if(x > 9){write(x / 10);
    }
    putchar(x % 10 + '0');
    FUCKER:;
}
/* ----------------------------------------------------------------------------------------------------------------------*/
const int maxn = 1e7 + 1;
int prime[maxn];
bool isprime[100000010];
signed main()
{
    int n , cnt = 0; read(n);int k ; read(k);
    memset(isprime , 1 , sizeof isprime);
    isprime[1] = 0;
    for(int i = 2 ; i <= n ; i ++)
    {
        if(isprime[i])
            prime[++cnt] = i;
        for(int j = 1 ; j <= cnt && i * prime[j] <= n ; j ++)
        {
            isprime[i * prime[j]] = 0;
            if(i % prime[j] == 0)
                break;
        }
    }

    for(int i = 1 ; i <= k ; i++)
    {
        int x ; 
        read( x );
        write( prime[x] );
        putchar('\n');
    }
    FUCKER:;
    return 0;
}