codepad

Language:

/*
  Name: Checking/generating Practical number
  Copyright: GNU
  Author: Debanjan Chanda
  Date: 08/11/09 13:26
  Description: Find the sum of divisors checking the sum >= <current divisor>
               if the final sum is greater than oe equal to num then return true
*/
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;
typedef unsigned long long int UL;
///////////////////////////////////////////////////////////////////////////////////////

#define rate
#define toogle /*Toogle between optimized and naive methods */
#define upto  /* Generate Practical number from upto the inputed range */
//#define checksingle /* Checking a particular number is practical or not */
//#define range /* Generate practical numbers between two inputs */

///////////////////////////////////////////////////////////////////////////////////////

//#define debug
//#define debug_1
//#define debug_2

///////////////////////////////////////////////////////////////////////////////////////

/* Parameter : UL
   returns : true if UL is practical;
             false if UL is not practical; */
#ifdef rate
#warning This is my program
#endif

bool isPractical(UL num){

if( num <= 0 ) return false; /* The practical number sequence starts from 1 */

if( num == 1) return true;

if((num&1)) return false;
   /*Any power of two is a practical number, because it trivially satisfies this
    characterization: the only prime in its factorization, p1, equals two as required.*/

if((num &(num - 1))== 0){/*If the control reaches here the number must be >0 so the
                               checking num>0 is avoided */
       //cout<<"I am power of two";
       return true;
   }
   UL i,
    sum = 0;

#ifndef toogle
  UL d = UL (num >> 1); /* num / 2 */
   for(i=1;i<=d;i++){
      if((num%i)==0){
        if((sum >= i-1)) sum += i;  /*This is impotant otherwise it will produce wrong output */
        else return false;
        #ifdef debug_1
         else {cout<<"num:"<<num<<" i:"<<i<<"\n";getchar();}  /* Some numbers 102 & 114 are not practical */
        #endif
     }
   }
 #endif

#ifdef toogle
   vector<UL> Divisors;
   //sum = 0;

Divisors.push_back(1);

for(i=2;i*i<=num;i++)
       {
         if(0 == (num%i)){
             if( i*i == num){
                Divisors.push_back(i);
                continue;
             }
         Divisors.push_back(i);
         Divisors.push_back(num/i);
         }
       }
     sort(Divisors.begin(),Divisors.end());
     UL size = Divisors.size();

#ifdef debug_2
     copy(Divisors.begin(),Divisors.end(),ostream_iterator<UL>(cout," "));
     cout<<"\n\n";
     getchar();
    #endif

for(i = 0; i<size; i++){
        if(sum >= Divisors[i]-1)
          sum+=Divisors[i];
       else
         return false;
     }

#endif

#ifdef debug
     cout<<"Sum:"<<sum<<"\n";
   #endif

if(sum >= num)return true;

return false;
}

int main(void)
{
UL num,
   Count = 0;

#ifdef checksingle
    cout<<"Enter a number: ";
    while((cin>>num) && (num>0))
#endif

#ifdef range
      UL low,up;
      cout<<"Enter low: ";
      cin>>low;
      cout<<"Enter up: ";
      cin>>up;
      for(num = low; num <= up; num++)
#endif

#ifdef upto
   UL rang;
   cout<<"Number of practical numbers:";
   cin>>rang;
   for(num = 1;Count < rang;num++)
#endif
   {
     if(isPractical(num)== true)
     #ifdef checksingle
       cout<<num<<" is practical\n";
    else
       cout<<num<<" is not practical\n";
     #endif

#ifndef checksingle
     cout<<++Count<<"  "<<num<<"\n";
     #endif

}
    #ifndef checksingle
       cout<<"Count:"<<Count;
    #endif
  return 0;
}

Private [?]

Run code