HJ56_iNOC产品部--完全数计算(C++)

推导公式
大数学家欧拉曾推算出完全数的获得公式：如果p是质数，且2^p-1也是质数，那么（2^p-1）X2^（p-1）便是一个完全数。
例如p=2，是一个质数，2^p-1=3也是质数，（2^p-1）X2^（p-1）=3X2=6，是完全数。
例如p=3，是一个质数，2^p-1=7也是质数，（2^p-1）X2^（p-1）=7X4=28，是完全数。
例如p=5，是一个质数，2^p-1=31也是质数，（2^p-1）X2^（p-1）=31X16=496是完全数。
当2^p-1是质数的时候，称其为梅森素数。到2013年2月6日为止，人类只发现了48个梅森素数，较小的有3、7、31、127等

//C++
#include <iostream>
#include <math.h>

using namespace std;

bool is_prime(int p);

// 如果p是质数，且2^p-1也是质数，那么（2^p-1）X2^（p-1）便是一个完全数
int main()
{
    int n;
    while(cin >> n)
    {
        int count = 0;
        for(int p=2; p<sqrt(n); p++)
        {
            long int t = pow(2,p)-1;
            if( is_prime(p) && is_prime(t) )
            {
                int perfect_num = pow(2,p-1) * t;
                if(  perfect_num>0 && perfect_num<n )
                    count++;
            }     
        }
        cout << count << endl;
    }
    return 0;
}

bool is_prime(int p)
{
    for(int i=2; i<sqrt(p); i++)
        if(p % i == 0)
            return false;
    return true;
}