#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; 
  }
  

评论