fork download
copy 
  1. //! (c) WhiZTiM __ionogu(<_at_)>acm.org
  2.  
  3. #include <cmath>
  4. #include <vector>
  5. #include <chrono>
  6. #include <iostream>
  7. #include <algorithm>
  8.  
  9. using uint64_t = std::uint64_t;
  10. template<typename Func, typename... Args>
  11. void timer(Func func, Args&&... args){
  12. 	auto start = std::chrono::high_resolution_clock::now();
  13. 	func(std::forward<Args&&>(args)...);
  14. 	auto stop = std::chrono::high_resolution_clock::now();
  15. 	std::cout.precision(8);
  16. 	std::cout << 
  17. 		"Took: " << std::chrono::duration<double, std::ratio<1,1>>(stop - start).count()
  18. 		<< " seconds\n";
  19. }
  20.  
  21. class SimplePrimeGenerator {
  22. public:		//intentional...
  23. 	std::vector<uint64_t> primes = {2, 3};
  24. 	std::size_t counter = 1;
  25. public:
  26. 	uint64_t compute(std::size_t index){
  27. 		if(index < primes.size())
  28. 			return primes[index];
  29. 		primes.reserve(index);
  30. 		for(; counter < index; counter++){
  31. 			uint64_t prime1 = (6*counter - 1);
  32. 			uint64_t prime2 = (6*counter + 1);
  33. 			if(not sub_prime_factor_exists_for(prime1))
  34. 				primes.emplace_back(prime1);	//then it is a prime
  35. 			if(not sub_prime_factor_exists_for(prime2))
  36. 				primes.emplace_back(prime2);	//ditto ^^
  37. 		}
  38. 		return primes[index];
  39. 	}
  40.  
  41. 	bool prime_factor_exists_for(uint64_t number) {
  42. 		if (not std::binary_search(primes.begin(), primes.end(), number))
  43. 			compute(std::sqrt(number) + 1);
  44. 		return std::binary_search(primes.begin(), primes.end(), number);
  45. 	}
  46.  
  47. 	inline bool sub_prime_factor_exists_for(uint64_t num) const {
  48. 		for(auto x : primes)
  49. 			if(num % x == 0 and num != x)
  50. 				return true;
  51. 		return false;
  52. 	}
  53. };
  54.  
  55. std::vector<std::size_t> simple_factors(uint64_t number){
  56. 	std::vector<std::size_t> rtn;
  57. 	std::size_t bound = std::sqrt(number);
  58. 	for(std::size_t i=1; i <= bound; i++)
  59. 		if(number % i == 0){
  60. 			rtn.emplace_back(i);
  61. 			rtn.emplace_back(number / i);
  62. 		}
  63. 	std::sort(rtn.begin(), rtn.end());
  64. 	return rtn;
  65. }
  66.  
  67. int mainc(){
  68. 	auto pf = simple_factors(600851475143ull);
  69. 	//auto pf = simple_factors(13195);
  70. 	SimplePrimeGenerator spg;
  71. 	for(auto k = pf.rbegin(); k != pf.rend(); ++k )
  72. 		if(spg.prime_factor_exists_for(*k)){
  73. 			std::cout << "Largest prime factor of 600851475143 is " << *k << "\n";
  74. 			break;
  75. 		}
  76. 	return 0;
  77. }
  78.  
  79. int main(){
  80. 	timer(mainc);
  81. 	return 0;
  82. }
Success #stdin #stdout 13.38s 3276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Largest prime factor of 600851475143 is 6857
Took: 13.441464 seconds
https://ideone.com/6Iu0fJ
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
language:
C++14 (gcc 8.3)
created:
9 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!