#include /* Prime numbers Formal Definition: n is prime if and only if it's evenly divisible by 1 and n */ // templatized template struct IsPrime{ static const bool result = N % D && IsPrime::result ; }; template struct IsPrime { static const bool result = true ; }; template struct IsPrime { static const bool result = true ; }; template::result > struct NextPrime{ static const uint64_t result = N+1; }; template struct NextPrime{ static const uint64_t result = NextPrime::result ; }; class End{}; template struct Primes{ static const uint64_t Head = NextPrime::result ; using Tail = Primes; }; template struct Primes<0,L>{ static const uint64_t Head = NextPrime::result ; using Tail = End; }; #include template void Print( bool isFirst = true ){ if ( isFirst ) std::cout << "["; else std::cout << ", "; std::cout << P::Head ; Print( false ); } template<> void Print( bool isFirst ){ std::cout << "]\n"; } // recursive bool rIsPrime( uint64_t n , uint64_t d = 0 ){ if ( d == 0 ) d = n - 1; if ( d < 2 ) return true ; return n%d && rIsPrime( n , d-1 ); } uint64_t rNextPrime( uint64_t n ){ if ( rIsPrime( n+1 ) ) return n+1; return rNextPrime( n+1 ); } uint64_t rNthPrime( uint64_t n , uint64_t i = 0 , uint64_t p = 0 ){ if ( n <= i ) return rNextPrime( p ); return rNthPrime( n , i + 1 , rNextPrime( p ) ); } // loop * sieve of Eratosthenes * #include /* * sieve * */ std::vector getPrimeSieve( uint64_t size ){ std::vector sieve( size , true ); sieve[0]=0; uint64_t iBound = size / 2; for ( uint64_t i = 2 ; i < iBound ; ++i ) if ( sieve[ i ] ) for ( uint64_t j = i * 2 ; j < size ; j += i ) sieve[ j ] = false ; std::vector serie; for ( uint64_t i = 0 ; i < size ; ++i) if ( sieve[ i ] ) serie.push_back( i ); return serie ; } #include void printCompare( std::vector table ){ std::cout << " * * Primes up to(n) result table loop vs recursion * *\n" << "nth" << std::setw(14) << std::right << "loop" << std::setw(11) << std::right << "rec\n"; for ( uint64_t i = 0 ; i < table.size() ; ++i ){ std::cout << std::setw(4) << std::right << i + 1; if ( (i+1)%10 == 1 ) std::cout << "st"; else if ( (i+1)%10 == 2 ) std::cout << "nd"; else if ( (i+1)%10 == 3 ) std::cout << "rd"; else std::cout << "th"; std::cout << std::setw(10) << std::right << table[ i ] << std::setw(10) << std::right << rNthPrime( i ) << "\n"; } } using namespace std; int main() { cout << "Compile time Primes<>\n"; cout << "IsPrime<4> : " << IsPrime<4>::result < : " << NextPrime<4>::result << endl; cout << "Primes<10> : "; typedef Primes<10> FirstTenPrimes ; Print< FirstTenPrimes >(); cout << endl; cout << rNthPrime (2); printCompare( getPrimeSieve( 30 ) ); cout << "\n\nLoop uses `Sieve of Eratosthenes` to find primes up to a number.\nFor example :\nprimes up to 1000: " ; vector data = getPrimeSieve( 1000 ); for ( auto i : data ) cout << i << " "; cout << endl << endl; return 0; }

Algorithms [Jhon Wells] Prime numbers