Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
src/math/primes/primes_basic.h
Go to the documentation of this file.
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
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines