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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
///
/// @file primecount.hpp
/// @brief primecount C++ API. primecount is a C/C++ library for
/// counting the number of primes <= x using highly optimized
/// implementations of the combinatorial type prime
/// counting function algorithms.
///
/// Copyright (C) 2025 Kim Walisch, <kim.walisch@gmail.com>
///
/// This file is distributed under the BSD License.
///
#ifndef PRIMECOUNT_HPP
#define PRIMECOUNT_HPP
#include <stdexcept>
#include <string>
#include <stdint.h>
#define PRIMECOUNT_VERSION "8.2"
#define PRIMECOUNT_VERSION_MAJOR 8
#define PRIMECOUNT_VERSION_MINOR 2
namespace primecount {
class primecount_error : public std::runtime_error
{
public:
primecount_error(const std::string& msg)
: std::runtime_error(msg)
{ }
};
/// pc_int128_t is a portable int128_t type used by primecount's C++ API.
///
/// How to convert a pc_int128_t to an int128_t:
/// int128_t n = x.lo | (int128_t(x.hi) << 64);
///
/// How to convert an int128_t to a pc_int128_t:
/// pc_int128_t x;
/// x.lo = (uint64_t) n;
/// x.hi = (int64_t) (n >> 64);
///
struct pc_int128_t
{
uint64_t lo;
int64_t hi;
};
/// Count the number of primes <= x using Xavier Gourdon's
/// algorithm. Uses all CPU cores by default.
/// Throws a primecount_error if an error occurs.
///
/// Run time: O(x^(2/3) / (log x)^2)
/// Memory usage: O(x^(1/3) * (log x)^3)
///
int64_t pi(int64_t x);
/// 128-bit prime counting function.
/// Count the number of primes <= x using Xavier Gourdon's
/// algorithm. Uses all CPU cores by default.
///
/// The 128-bit API automatically falls back to the 64-bit
/// implementation for x <= 2^63ā1. Therefore, there is no
/// performance penalty for using only the 128-bit API.
///
/// @pre x <= 10^31 on 64-bit systems and
/// x <= 2^63-1 on 32-bit systems.
/// Throws a primecount_error if an error occurs.
///
/// Run time: O(x^(2/3) / (log x)^2)
/// Memory usage: O(x^(1/3) * (log x)^3)
///
pc_int128_t pi(pc_int128_t x);
/// Find the nth prime using a combination of the prime counting
/// function and the sieve of Eratosthenes.
/// @pre n <= 216289611853439384
/// Throws a primecount_error if an error occurs.
///
/// Run time: O(x^(2/3) / (log x)^2)
/// Memory usage: O(x^(1/3) * (log x)^3)
///
int64_t nth_prime(int64_t n);
/// 128-bit nth prime function.
/// Find the nth prime using a combination of the prime counting
/// function and the sieve of Eratosthenes.
///
/// The 128-bit API automatically falls back to the 64-bit
/// implementation when appropriate. Therefore, there is
/// no performance penalty for using only the 128-bit API.
///
/// @pre n <= 10^29 on 64-bit systems and
/// n <= 216289611853439384 on 32-bit systems.
/// Throws a primecount_error if an error occurs.
///
/// Run time: O(x^(2/3) / (log x)^2)
/// Memory usage: O(x^(1/3) * (log x)^3)
///
pc_int128_t nth_prime(pc_int128_t n);
/// Partial sieve function (a.k.a. Legendre-sum).
/// phi(x, a) counts the numbers <= x that are not divisible
/// by any of the first a primes.
/// Throws a primecount_error if an error occurs.
///
int64_t phi(int64_t x, int64_t a);
/// Get the currently set number of threads
int get_num_threads();
/// Set the number of threads
void set_num_threads(int num_threads);
/// Recompute pi(x) with alternative alpha tuning factor(s) to
/// verify the first result. This redundancy helps guard
/// against potential bugs in primecount: if an error exists,
/// it is highly unlikely that both pi(x) computations would
/// produce the same (incorrect) result.
///
void set_double_check(bool enable);
/// Get the primecount version number, in the form āi.jā
std::string primecount_version();
} // namespace
#endif
|
