UVA1180 Perfect Numbers

Daitsat · 2023-12-22 19:08:07 · 题解

题目传送门：UVA1180 Perfect Numbers

题目大意：

判断 p 是否可以生成一个 2^{p-1}(2^p-1) 的完美数。

解释:　

• 这个问题涉及到欧几里得和完美数的关系。

• 欧几里得在他的《几何原本》一书中找到了所有偶数的完美数。

• 他证明了一个偶数是完美数的充分必要条件是它可以写成 2^{p-1}(2^p-1) 的形式，其中 p 和 2^{p-1} 都是素数。

• 根据这个定理，我们可以判断一个整数 p 是否生成一个完美数。

• 首先，我们计算 2^{p-1} 的值，如果它是素数，那么我们继续计算 2^{p-1}(2^p-1) 的值。如果这个值等于输入的整数 p，那么这个整数 p 生成一个完美数，否则不是。

  code：

  #include <bits/stdc++.h>
  using namespace std;
  int primes[] = {2, 3, 5, 7, 13, 17, 19};
  const int N = sizeof(primes) / sizeof(int);
  int main(){
    int t, p;
    char c;
    scanf("%d", &t);
    while(t--){
        scanf("%d%c", &p, &c);
        bool flag = false;
        for(int i = 0; i < N; i++){
            if(p == primes[i]){
                flag = true; 
                break;
            }
        }
        printf(flag ? "Yes\n" : "No\n");
    }
  
    return 0;
  }