Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
src/math/prime_sieve/eratosthenes_basic.h
Go to the documentation of this file.
00001 
00004 #include "utils/preconditions/preconditions.h"
00005 #include "utils/assert/integer_overflow.h"
00006 #include <limits>
00007 
00008 namespace math {
00009 namespace prime_sieve {
00010 
00019 class EratosthenesBasic {
00021   // Note: using upper-half of the range of SizeType is ok
00022   // as in this class we won't use difference type.
00023   typedef std::vector<bool>::size_type SizeType;
00024 
00025   public:
00032     template <typename T>
00033     void initialize(T t_size) {
00034       STATIC_ASSERT_CHECK_INTEGER_OVERFLOW<T, SizeType>();
00035       SizeType size = (SizeType) t_size;
00036       Preconditions::check(size > 2);
00037       // because of j = 2 * i
00038       Preconditions::check(size < std::numeric_limits<SizeType>::max() / 2,
00039           "Out of range for computation, there will be overflow");
00040       // and now we are ready to go
00041       data.resize(size);
00042       data[0] = false;
00043       data[1] = false;
00044       for (SizeType i = 2; i < size; i++) {
00045         data[i] = true;
00046       }
00047 
00048       for (SizeType i = 2; i < size; i++) if (data[i]) {
00049         for (SizeType j = 2 * i; j < size; j += i)
00050           data[j] = false;
00051       }
00052     }
00053 
00058     template <typename T>
00059     bool isPrime(T p) {
00060       STATIC_ASSERT_CHECK_INTEGER_OVERFLOW<T, SizeType>();
00061       Preconditions::checkRange((SizeType) p, data.size());
00062       return data[(SizeType) p];
00063     }
00064 
00065   private:
00066     std::vector<bool> data;
00067 };
00068 
00069 } // namespace prime_sieve
00070 } // namespace math
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines