012.cpp

Go to the documentation of this file.

#include <iostream>
using namespace std;

unsigned long
factor (unsigned long S)
{
  unsigned long no_of_factors = 1;
  unsigned power = 0;

  while (!(S &1)) //faster than S%2
    {
      S >>= 1; //faster than S/=2
      power++;
    }
  no_of_factors *= power + 1;

  power = 0;
  unsigned long last_factor = 3;
  for (unsigned long div = 3; S > 1 && S >= div;)
    {
      if (S % div != 0)         //skip if not divisible
        {
          div += 2;
          continue;
        }
      S /= div;
      if (div > last_factor)    //check divisibility of the same div again.
        {
          last_factor = div;
          no_of_factors *= power + 1;
          power = 1;
        }
      else
        power++;
    }
  //process the last factor
  if (S == 1)
    no_of_factors *= power + 1;
  return no_of_factors;
}

int
main ()
{
  unsigned long S = 1;
  for (int i = 1; factor (S) < 500; i++, S += i)
    {
    }
  cout << S << endl;
  return 0;
}