1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
// 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;
}
}
}
|
