Find the largest prime factor of a number. http://projecteuler.net/problem=3

largest-prime-factor.cc

#include <math.h>
#include <stdio.h>
#include <vector>

typedef std::vector<long> Queue;

long find_smallest_divisor(long number) {
  for (long i = 2; i < sqrt(number); ++i) {
    if (number % i == 0) {
      return i;
    }
  }
  return number;
}

void factorize(long number, Queue* queue) {
  for (long divisor = find_smallest_divisor(number);
       divisor != number;
       divisor = find_smallest_divisor(number)) {
    queue->push_back(divisor);
    number = number / divisor;
  }
  queue->push_back(number);
}

int main() {
  const long NUMBER = 600851475143;
  Queue q;
  factorize(NUMBER, &q);
  while (!q.empty()) {
    long factor = q.back();
    q.pop_back();
    if (find_smallest_divisor(factor) == factor) {
      printf("The largest prime factor of %ld is %ld", NUMBER, factor);
      return 0;
    }
  }
  return -1;
}