Grind Report 3

More Project Euler.

Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?


*WARNING: This contains the solution!*

This problem required a little more thought than the previous two. I do not remember the last time I did factoring, it must have been years before this. Too much Calculus!

One thing about factoring is that the composite number can be factored down to just about any prime number. Consequently we just have to try all of the prime numbers until one works. So this brings up the question, "How do you calculate a prime number?" After a little research I found that doing just this has been attempted over the centuries by many great minds and a proven formula has yet to be found.

My thought is that we will iterate though all odd numbers (since 2 is the only even prime). For each number we check see if the composite number is evenly divisible by that number. If it is then we can lessen the composite number down to composite / number. In order to have this work correctly a number must be repeated until it is no longer a factor of the composite. This will insure that only prime numbers are found.

How do we know when we have found the answer? One approach to this question is (I believe) that fact that the factor can square root of the composite. This is included in the solution from Project Euler. This definitely works; however, I came up with my own approach. Because I was lessening the composite number eventually the composite number would actually become a prime number and not just any prime number. It would become the largest prime number (since we are moving up). So I simply kept track of the product of all of the prime factors found up to a given point and once the product * composite would equal the original composite number it would return the "composite" as the solution.

One problem I ran into here is that the original composite number is so large that it requires a long long type. I attempted to figure out how to do division with long long but could not come up with anything that worked. I found some stuff using lldiv() from stdlib.h but that must have been for something else because it did not work when I included stdlib.h. Because of this I had to do the division with a calculator everytime it found a prime factor. If anyone knows how to do long long division I am all ears. Here is the code.

#include <iostream>
#include <stdlib.h>

using namespace std;

long long NUMBER = 600851475143;

void FindLargestPrime(long long composite)
{
//the number
int number = 2;
long long product = 1;
while (true)
{
 //check to see if the number evenly goes into the composite
 if (composite % number == 0)
 {
  //if so then set this to the new composite
  //this doesn't actually work but would if lldiv and lldiv_t were defined.
  lldiv_t compt = lldiv(composite, number);
  composite = compt.quot;
  //update the product
  product *= number;
 }
 else //is not a factor so increase the number
 {
  number += 2;
  if (number <= 4)     number -= 1;   }   //check to see if we have found the final prime factor   if (product != 1 && product * composite == NUMBER)    break;  }    cout << "Answer: " << composite << endl; }   int main() {  FindLargestPrime(NUMBER);  return 0; } 

*saved game*