fork(1) download
copy 
  1. #include <cstddef>
  2. #include <iostream>
  3.  
  4. template<bool debug>
  5. constexpr bool any_factors( std::size_t target, std::size_t start, std::size_t step ) {
  6.   if (debug)
  7.   {
  8. 	std::cout << "Target: " << target << ", start:" << start*6 << ", step:" << step << "\n";
  9.   }
  10.   if (start*start*36 > target)
  11.   {
  12. 	  if (debug)
  13. 	  {
  14. 	  	std::cout << "start*start> target, returning false\n";
  15. 	  }
  16. 	  return false;
  17.   }
  18.   if (step==1)
  19.   {
  20.     bool one_mod_6 = target%(start*6+1) == 0;
  21.     bool five_mod_6 = target%(start*6+5) == 0;
  22.     if (debug)
  23.     {
  24.     	std::cout << "target%6k+1=" << one_mod_6 << "\n";
  25.     	std::cout << "target%6k+5=" << five_mod_6 << "\n";
  26.     }
  27.     return one_mod_6 || five_mod_6;
  28.   }
  29.  
  30.   bool first_half = any_factors<debug>(target, start, step/2);
  31.   bool second_half = any_factors<debug>(target, start+ step/2, (step+1)/2);
  32.  
  33.   if (debug)
  34.   {
  35. 	std::cout << "Halves are " << first_half << second_half << "\n;";
  36.   }
  37.   return first_half || second_half;  
  38. }
  39. template<bool debug=false>
  40. constexpr bool is_prime( std::size_t target ) {
  41.   // handle 2, 3 and 5:
  42.   return 
  43.     target == 2 || target == 3 || target == 5 ||
  44.     (
  45.       target%2 != 0
  46.       && target%3 != 0
  47.       && target%5 != 0
  48.       && !any_factors<debug>( target, 1, (target+5)/6 )
  49.     ); // can make that upper bound a bit tighter, but I don't care
  50. }
  51. constexpr bool is_prime_dbg( std::size_t target ) {
  52.     return is_prime<true>(target);
  53. }
  54. int main() {
  55.     // 100103 
  56.     std::cout << "5:" << is_prime(5) << "\n";
  57.     std::cout << "10:" << is_prime(10) << "\n";
  58.     std::cout << "13:" << is_prime(13) << "\n";
  59.     std::cout << "91:" << is_prime(91) << "\n";
  60.     std::cout << "97:" << is_prime(97) << "\n";
  61.     std::cout << "19*19:" << is_prime(19*19) << "\n";
  62.     std::cout << "100103:" << is_prime(100103) << "\n";
  63. }
Success #stdin #stdout 0s 15232KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
5:1
10:0
13:1
91:0
97:1
19*19:0
100103:1
https://ideone.com/qIunvM
language:
C++14 (gcc 8.3)
created:
6 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!