fork download
copy 
  1. /* (c) WhiZTiM ionogu (<_aT_>)acm(<dot>)org
  2.    Thanks to Kenneth Nnani Ifeanyi
  3. */
  4.  
  5. #include <chrono>
  6. #include <vector>
  7. #include <iostream>
  8. #include <algorithm>
  9.  
  10. using uint = unsigned int;
  11.  
  12. template<typename Func, typename... Args>
  13. void timer(Func func, Args&&... args){
  14. 	auto start = std::chrono::high_resolution_clock::now();
  15. 	func(std::forward<Args&&>(args)...);
  16. 	auto stop = std::chrono::high_resolution_clock::now();
  17. 	std::cout.precision(8);
  18. 	std::cout << 
  19. 		"Took: " << std::chrono::duration<double, std::ratio<1,1>>(stop - start).count()
  20. 		<< " seconds\n";
  21. }
  22.  
  23.  
  24. std::vector<uint> sieve(uint limit=1'000'000)
  25. {
  26.     std::vector <uint> rtn;
  27.     bool flag[1000000];
  28.     flag[0] = true;
  29.     flag[1] = true;
  30.     for(uint i = 2; i < 1000000; i++)
  31.     {
  32.         if(not flag[i])
  33. 	{
  34. 	    // do all multiples
  35. 	    for(int j = 2*i; j <= 1000000; j+=i)
  36. 		flag[j] = true;
  37. 	}
  38.     }
  39.  
  40.     for(uint i = 0; i <= 1000000; i++)
  41.         if(not flag[i])
  42. 	    rtn.push_back(i);
  43.     return rtn;
  44. }
  45.  
  46. void run()
  47. {
  48.    std::ios_base::sync_with_stdio(0);
  49.    auto a = sieve();
  50.    long long int n = 600851475143 ;
  51.     ///assumied all factors are less than 1000000
  52.     std::vector <uint> result;
  53.     while(n != 1)
  54.     {
  55.         for(uint i = 0; i < a.size(); i++)
  56.         {
  57.             if(n%a[i] == 0){result.push_back(a[i]); n = n/a[i]; break;}
  58.         }
  59.     }
  60.     auto maxx = std::max_element(result.begin(), result.end());
  61.     std::cout << "maximum factor is: " << *maxx << std::endl;
  62. }
  63.  
  64. int main()
  65. {
  66.     timer(run);
  67.     return 0;
  68. }
  69.  
Success #stdin #stdout 0.01s 4248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
maximum factor is: 6857
Took: 0.016968057 seconds
https://ideone.com/n0CVvD
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

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!