#include <iostream>   #include <algorithm>   #include <vector>   #include <iterator>     template <typename T>  class PrimerCache   {       typedef T   ValueType;      typedef std::vector<ValueType> IntArray;       typedef typename IntArray::const_iterator IntPtr;          static IntArray mCache;          protected:       bool Test(ValueType num) const       {           // make sure : half  < mCache.back()           // !!! IncreaseCache(half) promised this !!!                     ValueType half = num / 2 + 1;                    for(IntPtr i = mCache.begin(); *i < half && i != mCache.end();  ++i)           {               if( num % (*i) == 0)               {                    return false;               }           }                   return true;       }          void IncreaseCache(ValueType num) const      {           ValueType upper = mCache.back();                      while (upper < num)           {               upper++;                           if( Test(upper))               {                   mCache.push_back(upper);               }                          }               }          bool InCache(ValueType num) const      {           return std::binary_search(mCache.begin(), mCache.end(), num);       }   public:       PrimerCache(ValueType lowerNum = 1000)      {           IsPrimer(lowerNum);       }          bool IsPrimer(ValueType num) const      {           ValueType biggestPrimer = mCache.back() + 1;              if( biggestPrimer > num)           {               return InCache(num);           }           else           {               IncreaseCache(num);               return Test(num);            }       }       friend std::ostream& operator<<(std::ostream& out, PrimerCache const& primerCache) -     {           IntArray& cache = primerCache.mCache;          out << "Primer Cache Has " << cache.size() << " elements, they are " << std::endl;            std::copy(cache.begin(), cache.end(), std::ostream_iterator<int>(out, ","));           return out;       }   };  //the one and only cache;  template <typename T>  typename PrimerCache<T>::IntArray PrimerCache<T>::mCache = IntArray(1, 2);     template <typename CacheType>  void TestPrimer(CacheType& cache, int num)   {       int test = num;       std::cout<< test << " is primer? "<< std::boolalpha << cache.IsPrimer(test) << std::endl;   }         int main()   {       PrimerCache<int> primer;       int test;          TestPrimer(primer, 1);       TestPrimer(primer, 2);       TestPrimer(primer, 4);       TestPrimer(primer, 5);       TestPrimer(primer, 99);       TestPrimer(primer, 97);       TestPrimer(primer, 101);       TestPrimer(primer, 102);       TestPrimer(primer, 98);       TestPrimer(primer, 96);                 std::cout << primer << std::endl;         std::cout << "primer is " << sizeof ( PrimerCache<int>) << std::endl;        PrimerCache<short> p(10);            TestPrimer(p, 1);      TestPrimer(p, 2);        std::cout << p << std::endl;      return 0;   }  

评论