1
2
3
4
5
6 #include <soulng/util/Prime.hpp>
7 #include <boost/multiprecision/miller_rabin.hpp>
8
9 namespace soulng { namespace util {
10
11 bool IsPrime64(uint64_t n)
12 {
13 if (n <= 1) return false;
14 if (n <= 3) return true;
15 if (n % 2 == 0 || n % 3 == 0) return false;
16 for (uint64_t i = 5; i * i <= n; i = i + 6)
17 {
18 if (n % i == 0 || n % (i + 2) == 0)
19 {
20 return false;
21 }
22 }
23 return true;
24 }
25
26 void NextPrime(boost::multiprecision::uint128_t& x)
27 {
28 ++x;
29 constexpr uint64_t max64 = std::numeric_limits<uint64_t>::max();
30 while (x < max64)
31 {
32 uint64_t n = static_cast<uint64_t>(x);
33 if (IsPrime64(n))
34 {
35 return;
36 }
37 ++x;
38 }
39 while (!boost::multiprecision::miller_rabin_test(x, 25))
40 {
41 ++x;
42 }
43 }
44
45 } }