Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
00001 00004 #include "utils/preconditions/preconditions.h" 00005 #include <vector> 00006 #include <algorithm> 00007 #include <cmath> 00008 00009 namespace math { 00010 namespace prime_sieve { 00011 00012 // Optimized implementation of Eratosthenes sieve. 00013 // Running time is O(n log log n). 00014 class EratosthenesOptimized { 00015 public: 00016 void initialize(int size_) { 00017 Preconditions::check(size_ > 2); 00018 // Note: this won't set the elements to true on downsizing 00019 // only sets new elements when upsizing. 00020 // But in this algorithm, it is ok! 00021 data.resize(size_ / 2 + 1, true); 00022 size = size_; 00023 00024 data[0] = false; 00025 00026 // Note: size >= 3 implies sqrt(size) + 1 < size 00027 // and we are safe when indexing data[i] 00028 int sqrtsize = (int) sqrt(size) + 1; 00029 00030 for (int i = 1; i < sqrtsize; i++) 00031 if (data[i]) { // eliminate only from primes 00032 // we can start eliminating from p^2 = (2 * i + 1)^2 00033 // which corresponds to data[2 * i^2 + 2 * i] 00034 for (int j = 2 * i * (i + 1); j < size / 2; j += 2 * i + 1) { 00035 data[j] = false; 00036 } 00037 } 00038 } 00039 00040 // Note: you may query for range [0, size) 00041 bool isPrime(int p) { 00042 Preconditions::checkRange(p, size); 00043 if (p % 2 == 0) { 00044 return p == 2 ? true : false; 00045 } 00046 return data[p/2]; 00047 } 00048 00049 private: 00050 // Note: if you know maximum range in advance, use bitset<MAX/2> 00051 // instead of vector<bool>; 00052 // Internal representation is that data contains only info 00053 // about primality of odd numbers so the correspondence is 00054 // data[0]<->1, data[1]<->3, data[2]<->5, ... 00055 // @see isPrime implementation 00056 std::vector<bool> data; 00057 int size; 00058 }; 00059 00060 } // namespace prime_sieve 00061 } // namespace math