UVA1180 Perfect Numbers题解

sqh_let_it_be · 2021-11-30 21:10:07 · 题解

打表大法好

那两个题解已经把完美数的规律说出来了，那我就按照他们的思路打一波表，毕竟只有 33 个数。

如果 p 为质数，2^p-1 是质数，那么（2^p-1）(2^{p-1}) 就是完全数。

简而言之，就是判断 p 和 2^p-1 是不是质数就行了。

打表程序：

#include<bits/stdc++.h>
using namespace std;
long long int n;
bool flag=true;
int main()
{
    freopen("dabiao.txt","w",stdout);
    cout<<"1 No"<<endl;
    for(int i=2;i<=33;i++)
    {
        flag=true;
        n=pow(2,i)-1;
        for(int j=2;j*j<=i;j++)
          if(i%j==0)
            flag=false;//如果 p 不是素数
        for(long long int j=2;j*j<=n;j++)
          if(n%j==0)
            flag=false;//如果 2^p -1 不是素数
        if(flag==true)
          cout<<i<<" Yes"<<endl;
        else
          cout<<i<<" NO"<<endl;
    }
}

然后将给的结果放到程序里面：

#include<iostream>
#include<cstdio>
using namespace std;
char ch;
int n,p;
int main()
{
    cin>>n;
    for(int k=1;k<=n;k++)
    {
        cin>>p>>ch;//UVA的格式是真的难受
        if(p==2||p==3||p==5||p==7||p==13||p==17||p==19||p==31)
          cout<<"Yes"<<endl;
        else
          cout<<"No"<<endl;
    }
    return 0;
}