003.cpp

Go to the documentation of this file.

#include <iostream>
#include <cmath>
using namespace std;

unsigned ten = 1e4;
class largeN
{
  unsigned a, b, c, d;
  //N = a*ten^3 + b*ten^2 + c*ten + d
public:unsigned sqrtN;

    largeN (int w, int x, int y, int z)
  {
    a = w;
    b = x;
    c = y;
    d = z;
    sqrtN = sq_root ();
  }

  unsigned remainder (unsigned k)
  {
    unsigned a1 = a % k;
    unsigned b1 = (a1 * ten + b) % k;
    unsigned c1 = (b1 * ten + c) % k;
    return (c1 * ten + d) % k;
  }
  largeN divide (unsigned k)
  {
    unsigned r;                 //remainder 

    unsigned a1 = a / k;
    r = a % k * ten + b;
    unsigned b1 = r / k;
    r = r % k * ten + c;
    unsigned c1 = r / k;
    r = r % k * ten + d;
    unsigned d1 = r / k;
    return largeN (a1, b1, c1, d1);
  }
  double sq_root ()             //just an estimation
  {
    if (b != 0) //division by zero if a=b=0
      {
        double factor = (1 + (double (c) * 1e4 + d) /2e8 / (double (a) * 1e4 + b));//usually equal to 1
        return factor * sqrt (c * ten + d);
      }
    else
      return sqrt (c * ten + d);
  }
  void print ()
  {
    cout << '(' << a << ',' << b << ',' << c << ',' << d << ')';
  }

};

int
main ()
{

  largeN N (0, 6008, 5147, 5143);
cout << "smallest factor    upper_limit  number_N";
//find smallest factor
  unsigned upper_limit;
  //loop through to find the 2nd smallest factor..., etc.
  do
    {
      upper_limit = N.sqrtN + 1;
      unsigned k;
      for (k = 3; k <= upper_limit; k+=2)//I bet there's no even prime factor
        if (N.remainder (k) == 0)//k is the smallest factor
          {
            cout << k << "    " << upper_limit << "  "; 
            N.print ();
            cout << endl;
            N = N.divide (k);
            break;
          }
      if (k > upper_limit)
        {
          cout << "*    " << upper_limit << "  ";
          N.print ();
          cout << endl;
          break;
        }
    }
  while (upper_limit >= 3);//just for safety

N.print();
cout << " is the largest prime factor." << endl;
  return 0;
}