primes.cpp

来自「unix/linux下拼写检查程序源码」· C++ 代码 · 共 52 行

// Copyright (c) 2000
// Kevin Atkinson
//
// Permission to use, copy, modify, distribute and sell this software
// and its documentation for any purpose is hereby granted without
// fee, provided that the above copyright notice appear in all copies
// and that both that copyright notice and this permission notice
// appear in supporting documentation. Kevin Atkinson makes no
// representations about the suitability of this software for any
// purpose.  It is provided "as is" without express or implied
// warranty.

#include "primes.hpp"
#include <cmath>
#include <cassert>

namespace aspeller {

  using namespace std;

  void Primes::resize(size_type s) {
    size_type i, j = 2;
    data.resize(s);
    for(i = 0; i < s; ++i) 
      data[i] = true;
    if (s > 0)
      data[0] = false;
    if (s > 1)
      data[1] = false;
    size_type sqrt_s = static_cast<size_type>(sqrt(static_cast<double>(s)));
    while (j < sqrt_s) {
      for (i = 2*j; i < s; i += j) {
	data[i] = false;
      }
      ++j;
      for (;j < sqrt_s && !data[j]; ++j);
    }
  }

  bool Primes::is_prime(size_type n) const {
    if (n < size()) {
      return data[n];
    } else {
      size_type e = static_cast<size_type>(sqrt(static_cast<double>(n)));
      assert(e < size());
      for (const_iterator i = begin(); *i <= e; ++i) 
	if (!(n % *i)) return false;
      return true;
    }
  }
}