fork download 
  1. #include <cstddef>
  2. #include <iostream>
  3.  
  4. template<bool b>
  5. constexpr std::size_t dbg(std::size_t in) {
  6.     return b?((std::cout << in << ","), void(), in):in;
  7. }
  8. template<bool b>
  9. constexpr bool dbg_ln(bool in) {
  10.     return b?((std::cout << in << ")\n"), void(), in):in;
  11. }
  12. template<bool b>
  13. constexpr std::size_t dbg_start(std::size_t in) {
  14.     return b?((std::cout << "(start:" << in << ","), void(), in):in;
  15. }
  16. template<bool b>
  17. constexpr std::size_t dbg_target(std::size_t in) {
  18.     return b?((std::cout << "target:" << in << ","), void(), in):in;
  19. }
  20. template<bool b>
  21. constexpr std::size_t dbg_step(std::size_t in) {
  22.     return b?((std::cout << "step:" << in << ","), void(), in):in;
  23. }
  24. template<bool b>
  25. constexpr bool dbg_rec(bool in) {
  26.     return b?((std::cout << "rec:" << in << ","), void(), in):in;
  27. }
  28. template<bool b>
  29. constexpr bool dbg_check(bool in) {
  30.     return b?((std::cout << "chk:" << in << ","), void(), in):in;
  31. }
  32. template<bool debug>
  33. constexpr bool any_factors( std::size_t target, std::size_t start, std::size_t step ) {
  34.   return dbg_ln<debug>(
  35.       !(dbg_start<debug>(start)*start*36 > dbg_target<debug>(target))
  36.   &&
  37.   (
  38.     ( (dbg_step<debug>(step)==1)
  39.       && (
  40.         dbg_check<debug>(target%(start*6+1) == 0)
  41.         || dbg_check<debug>(target%(start*6+5) == 0)
  42.       )
  43.     )
  44.     ||
  45.     ( (dbg_step<debug>(step) > 1)
  46.       &&
  47.       (
  48.         dbg_rec<debug>(any_factors<debug>( target, start, step/2 ))
  49.         || dbg_rec<debug>(any_factors<debug>( target, start+step/2, step-step/2 ))
  50.       )
  51.     )
  52.   ));
  53. }
  54. template<bool debug>
  55. constexpr bool is_prime_( std::size_t target ) {
  56.   // handle 2, 3 and 5:
  57.   return 
  58.     target == 2 || target == 3 || target == 5 ||
  59.     (
  60.       target%2 != 0
  61.       && target%3 != 0
  62.       && target%5 != 0
  63.       && !any_factors<debug>( target, 1, target/6 + 1 )
  64.     ); // can make that upper bound a bit tighter, but I don't care
  65. }
  66. constexpr bool is_prime( std::size_t target ) {
  67.     return is_prime_<false>(target);
  68. }
  69. constexpr bool is_prime_dbg( std::size_t target ) {
  70.     return is_prime_<true>(target);
  71. }
  72. int main() {
  73.     // 100103 
  74.     std::cout << "5:" << is_prime(5) << "\n";
  75.     std::cout << "10:" << is_prime(10) << "\n";
  76.     std::cout << "13:" << is_prime(13) << "\n";
  77.     std::cout << "91:" << is_prime(91) << "\n";
  78.     std::cout << "97:" << is_prime(97) << "\n";
  79.     std::cout << "19*19:" << is_prime(19*19) << "\n";
  80.     std::cout << "100103:" << is_prime(100103) << "\n";
  81. }
Success #stdin #stdout 0s 15232KB
comments (?)
stdin 
Standard input is empty
stdout 
5:1
10:0
13:1
91:0
97:1
19*19:0
100103:1
https://ideone.com/sbB4Qs
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!