Advertisement
alfps

Infinite sequence of prime numbers

Apr 7th, 2021
671
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.28 KB | None | 0 0
  1. #include <kickstart/all.hpp>
  2. using namespace kickstart::all;
  3.  
  4. #include <queue>
  5. #include <vector>
  6.  
  7. template< class Item, class Compare_func >
  8. using Priority_q = std::priority_queue<Item, std::vector<Item>, Compare_func>;
  9.  
  10. struct Multiple
  11. {
  12.     int base; int n;
  13.     auto value() const -> int{ return n*base; }
  14. };
  15.    
  16. struct Descending_order
  17. {
  18.     auto operator()( const Multiple& a, const Multiple& b ) const
  19.         -> bool
  20.     { return a.value() > b.value(); }       // Note: direction of comparison.
  21. };
  22.  
  23. auto main() -> int
  24. {
  25.     out << 2;
  26.     auto larger_composites = Priority_q<Multiple, Descending_order>();
  27.     larger_composites.push( Multiple{2, 2} );
  28.     for( int current = 3; /*current < 100*/; ++current ) {
  29.         bool is_composite = false;
  30.         for( ;; ) {
  31.             const Multiple next_composite = larger_composites.top();
  32.             if( current < next_composite.value() ) {
  33.                 break;
  34.             }
  35.             larger_composites.pop();
  36.             is_composite = true;
  37.             larger_composites.push( Multiple{next_composite.base, 1 + next_composite.n} );
  38.         }
  39.         if( not is_composite ) {
  40.             out << ' ' << current;
  41.             larger_composites.push( Multiple{current, 2} );
  42.         }
  43.     }
  44.     /*out << endl;*/
  45. }
  46.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement