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