project-euler

https://projecteuler.net/
Log | Files | Refs | README

Euler_3.cpp (800B)

      1 #include <algorithm>
      2 
      3 #include "Euler.h"
      4 
      5 llui lpf(llui x)
      6 {
      7     bool is_prime;
      8 
      9     llui count = 1;
     10 
     11     for(llui i = 3; count < x; i += 2)
     12     {
     13         is_prime = true;
     14 
     15         for(llui j = 3; j * j <= i && is_prime; j += 2)
     16             if(i % j == 0) is_prime = false;
     17 
     18         if(is_prime) {
     19             if (x % i == 0)
     20                 return i;
     21 
     22             ++count;
     23         }
     24     }
     25 
     26     return 0; //prime factor does not exist (1 does not count as prime)
     27 }
     28 
     29 llui Euler::LargestPrimeFactor()
     30 {
     31     std::vector<llui> primes;
     32 
     33     primes.push_back(1);
     34 
     35     llui x = 600851475143;
     36 
     37     while (x > 1)
     38     {
     39         x /= primes.back();
     40 
     41         llui y = lpf(x);
     42 
     43         if (y != 0)
     44             primes.push_back(y);
     45     }
     46 
     47     std::sort (primes.begin(), primes.end());
     48 
     49     return primes.back();
     50 }