fork download
copy 
  1. #include <cstdint>
  2. #include <iostream>
  3. #include <cmath>
  4. #include <vector>
  5.  
  6. bool prime( std::uintmax_t number, const std::vector<bool>& sieve )
  7. {
  8.     const std::size_t SZ = std::ceil( std::sqrt(number) ) + 1 ;
  9.     for( std::size_t i = 2 ; i < SZ ; ++i )
  10.         if( sieve[i] && !(number%i) ) return false ;
  11.     return true ;
  12. }
  13.  
  14. int main()
  15. {
  16.     std::uintmax_t N ;
  17.     if( std::cout << "N? " && std::cin >> N )  // 600851475143 ;
  18.     {
  19.         const std::size_t SZ = std::ceil( std::sqrt(N) ) + 1 ;
  20.  
  21.         // generate a prime number sieve upto the square root of N
  22.         std::vector<bool> sieve( SZ, true ) ;
  23.         for( std::size_t i = 2 ; i < SZ ; ++i ) if( sieve[i] )
  24.               for( auto j = i*i ; j < SZ ; j += i ) sieve[j] = false ;
  25.  
  26.         std::uintmax_t largest_prime_factor = 1 ;
  27.  
  28.         // start with 1 because N may be a prime
  29.         for( std::size_t i = 1 ; i < SZ ; ++i ) if( sieve[i] && N%i == 0 )
  30.         {
  31.             if( prime( N/i, sieve ) )
  32.             {
  33.                largest_prime_factor = N/i ;
  34.                break ; // N == x*i, x>sqrt(i), and x is a prime
  35.             }
  36.             else largest_prime_factor = i ;
  37.         }
  38.  
  39.         std::cout << "largest prime factor of " << N << " is "
  40.                    << largest_prime_factor << '\n' ;
  41.     }
  42. }
  43.  
Success #stdin #stdout 0.01s 3036KB
comments (?)
stdin
copy 
600851475143
stdout
copy 
N? largest prime factor of 600851475143 is 6857
https://ideone.com/DG2zY9
language:
C++14 (gcc 8.3)
created:
10 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!