fork(1) download
  1. #include <iostream>
  2. #include <cmath>
  3. #include <chrono>
  4. #include <iomanip>
  5. #include <sstream>
  6. #include <string>
  7.  
  8. #define endl '\n'
  9.  
  10. bool is_prime(unsigned n) {
  11. if(n == 2 || n == 3) return true;
  12. if(n % 2 == 0 || n % 3 == 0) return false;
  13.  
  14. unsigned i=5, w=2;
  15.  
  16. while(i*i <= sqrt(n)) {
  17. if(n%i == 0) return false;
  18.  
  19. i += w;
  20. w = 6-w;
  21. }
  22. return true;
  23. }
  24.  
  25. std::string ftos(float f, int precision = 5) {
  26. std::stringstream ss;
  27. ss << std::fixed << std::setprecision(precision) << f;
  28. return ss.str();
  29. }
  30.  
  31. int main() {
  32.  
  33. unsigned max = 10000000, counters_found = 0;
  34. bool flag = false;
  35.  
  36. auto start = std::chrono::high_resolution_clock::now();
  37.  
  38. // iterate thru odd numbers n
  39. for(unsigned i=3; i <= max; i += 2){
  40.  
  41. for(unsigned j=1; j<i; j++) {
  42. if(is_prime(j*j + (i-j)*(i-j))) {
  43. flag = true;
  44. //std::cout << j << "^2 + " << (i-j) << "^2 is prime (" << i << ")" << endl;
  45. break;
  46. }
  47. }
  48. if(!flag) {
  49. std::cout << "counter: " << i << endl;
  50. ++counters_found;
  51. }
  52. flag = false;
  53. }
  54.  
  55. auto end = std::chrono::high_resolution_clock::now();
  56. auto duration = std::chrono::duration_cast<std::chrono::duration<double>>(end-start);
  57. std::cout << counters_found
  58. << " counter(s) found for n <= "
  59. << max
  60. << ". \nSearch took "
  61. << ftos(duration.count(), 5)
  62. << " second(s) and approximately "
  63. << ftos(duration.count() / max, 10)
  64. << " second(s) per integer."
  65. << endl;
  66.  
  67. return 0;
  68. }
Success #stdin #stdout 1.63s 15240KB
stdin
Standard input is empty
stdout
0 counter(s) found for n <= 10000000. 
Search took 1.63438 second(s) and approximately 0.0000001634 second(s) per integer.