Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
00001 #ifndef H_MATH_PRIMES_PRIMES_BASIC 00002 #define H_MATH_PRIMES_PRIMES_BASIC 00003 00007 #include "utils/preconditions/preconditions.h" 00008 namespace math { 00009 namespace primes { 00010 00014 class PrimesBasic { 00015 public: 00017 typedef long long int BaseType; 00018 00026 static bool isPrime(BaseType p) { 00027 Preconditions::check(p > 0, "tested integer should be positive!"); 00028 // Note: following check is to ensure that i*i in the 00029 // rest of the code do not overflow. 00030 // Hovewer, this check is very rough and can be relaxed a bit. 00031 if (p >= std::numeric_limits<BaseType>::max() / 2) { 00032 throw std::overflow_error("tested integer is too big!"); 00033 } 00034 if (p == 1) { 00035 return false; 00036 } 00037 BaseType i = 2; 00038 // This is reformulation of i <= sqrt(p) 00039 // We do this transformation for two reasons 00040 // a) (int) sqrt(n*n) where n is prime may give wrong result if badly 00041 // rounded 00042 // b) 64bit number doesn't fit into double and we may loose some digits! 00043 while (i * i <= p) { 00044 if (p % i == 0) { 00045 return false; 00046 } 00047 i++; 00048 } 00049 // now i > sqrt(p) 00050 return true; 00051 } 00052 }; 00053 00054 } // namespace primes 00055 } // namespace math 00056 #endif