fork download
copy 
  1. /*
  2.  
  3. Calculates the highest prime factor of 600,851,475,143.
  4.  
  5. */
  6.  
  7. #include<iostream>
  8. #include <cmath>
  9. using namespace std;
  10.  
  11. bool is_prime(const unsigned long long);
  12.  
  13. int main(){
  14.   //Program assumes a is not even
  15.    const  unsigned long long  a=600851475143;
  16.   //       const  unsigned long long  a=533;
  17.   // largest prime factor of 533 is 41
  18.  
  19.   const   unsigned long long sqrta=pow(a, 0.5);
  20.  
  21.   unsigned long long sqrta_tmp = sqrta;
  22.  
  23.   if((sqrta % 2) == 0) sqrta_tmp--;
  24.  
  25.   const unsigned long long sqrta_madeodd = sqrta_tmp;
  26.   //to make it odd
  27.  
  28.   const unsigned long long  MAX = a/7-1;
  29.   // MAX needs to be odd. MAX is the largest possible prime factor
  30.  
  31.   unsigned long long i;
  32.  
  33.   cout << MAX <<endl;
  34.   cout << sqrta << endl;
  35.  
  36.   bool found = false;
  37.  
  38.   //Case 1 where  the max prime factor is bigger than sqrta
  39.   //we iterate over the lower factor because then we only need to have
  40.   //sqrt iterations
  41.   //Note the increasing order of the loop
  42.   for(i=7; i <sqrta; i= i+2){
  43.     if((a%i == 0) && is_prime(a/i)){
  44.       found = true;
  45.       cout <<"The largest prime factor of " <<a <<" is " <<a/i <<endl;
  46.       return 0;
  47.     }
  48.   }
  49.  
  50.  
  51. //Case 2 where the max prime factor is less than or equal to sqrta
  52.   //Note the decreasing order of the loop 
  53.   //And note the odd starting number
  54.   for(i= sqrta_madeodd; i >=7; i= i-2){
  55.     if((a%i == 0) && is_prime(i)){
  56.       found = true;
  57.       cout <<"The largest prime factor of " <<a <<" is " <<i <<endl;
  58.       return 0;
  59.     }
  60.   }
  61.  
  62.   //if we are here then no prime factor found.
  63.   cout <<a <<" is a prime." <<endl;
  64.   return 0;
  65. }
  66.  
  67. bool is_prime(const unsigned long long num) {
  68.   // checks if num is prime, given odd num geq 3
  69.   unsigned long long fac;
  70.   const unsigned long long fac_max = pow(num, 0.5);
  71.   //max factor to check for in prime test
  72.  
  73.   cout <<"Checking for primality " << num << endl;
  74.   for(fac=3; fac <=fac_max; fac= fac+2)
  75.     if((num % fac) == 0) {
  76.       cout <<"Factor in primality: ";
  77.       cout << fac <<endl; 
  78.       return(false);
  79.     }
  80.  
  81.   return true;
  82. }
  83.  
  84.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:15: error: integer constant is too large for ‘long’ type
stdout
copy 
Standard output is empty
https://ideone.com/gOj36
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!