UVA 10490 - Mr. Azad and his Son!!!!! solution

problem link-click here

solving this problem i have learnt a new rule which is proved by Euclid, a well-known mathematician. the rule is that  2^(p-1)(2^p − 1) is a perfect number whenever 2^p − 1 is prime. 

where p is an integer.


for more information regarding perfect numbers have a look here,
https://en.wikipedia.org/wiki/Perfect_number#Even_perfect_numbers


we need to precalculate power of 2 till 31 which means till 2^31 and store them in a vector array. one important thing is use unsigned long long here to get desired result.


an accepted output is given below:


#include<bits/stdc++.h>

#define s 33

using namespace std;


bool arr[s];

vector<long long int> v;


void sieve()

{

for(int i=2;i*i<=s;i++)

{

if(arr[i]==0)

{

for(int j=2;i*j<=s;j++)

{

arr[i*j]=1;

}

}

}

}


void power()

{

v.push_back(0);

v.push_back(2);


for(int i=2;i<=31;i++)

{

v.push_back(v[i-1]*2);

}

}


bool isprime(int n)

{


for(int i=2;i<=pow(n,0.5);i++)

{

if(n%i==0)

{

return false;

}

}


return true;

}


int main()

{

sieve();

power();


int n;


while(cin>>n && n!=0)

{

unsigned long long int a;


a=v[n-1]*(v[n]-1);


if(isprime((v[n]-1)))

{

cout<<"Perfect: "<<a<<"!"<<endl;

}

else if(arr[n]==0 && !isprime((v[n]-1)))

{

cout<<"Given number is prime. But, NO perfect number is available."<<endl;

}

else

{

cout<<"Given number is NOT prime! NO perfect number is available."<<endl;

}

}


return 0;
}