Zachary Stence

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

What is the largest prime factor of the number 600851475143 ?

I first solved this problem September 15th, 2014 in my AP Computer Science class in highschool. I do not have the original code I wrote, but I have redone the solution and included it below.

To solve this problem I first wrote a simple function to check whether a given number is prime or composite. It works by iterating through all possible divisors of a number, and if none divide it, it is prime. From there I iterate through numbers starting at the square root of 600851475143 and breaking at the first prime divisor.

#include <iostream>
#include <cmath>

const long NUM = 600851475143;

/**
 * Returns true if x is prime, false otherwise.
 * @param x: A positive integer 
 */
bool isPrime(int x) {
  // 1 is not prime; false for non-positive integers
  if (x <= 1) return false;
  // 2 is prime
  else if (x == 2) return true;
  else if (x % 2 == 0) return false;
  else {
    // iterate through all odd nums less than square root of x
    for (int i = 3; i <= sqrt(x); i += 2)
      // if x is divisible by a number, it is not prime
      if (x % i == 0) return false;
    return true;
  }
}

int main() {
  // iterate through possible divisors
  for (int i = floor(sqrt(NUM)); i > 0; i--) {
    // if i is a divisor and it is prime, answer found
    if (NUM % i == 0 && isPrime(i)) {
      std::cout << i << std::endl;
      break;
    }
  }
}

Answer: 6857