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
130
131
|
/*
* @file primecount.h
* @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_H
#define PRIMECOUNT_H
#include <stdbool.h>
#include <stdint.h>
#define PRIMECOUNT_VERSION "8.2"
#define PRIMECOUNT_VERSION_MAJOR 8
#define PRIMECOUNT_VERSION_MINOR 2
#ifdef __cplusplus
extern "C" {
#endif
/*
* 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);
*/
typedef struct {
uint64_t lo;
int64_t hi;
} pc_int128_t;
/*
* Count the number of primes <= x using Xavier Gourdon's
* algorithm. Uses all CPU cores by default.
* Returns -1 if an error occurs.
*
* Run time: O(x^(2/3) / (log x)^2)
* Memory usage: O(x^(1/3) * (log x)^3)
*/
int64_t primecount_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.
* @return -1 if an error occurs, else the number of primes <= x.
*
* Run time: O(x^(2/3) / (log x)^2)
* Memory usage: O(x^(1/3) * (log x)^3)
*/
pc_int128_t primecount_pi_128(pc_int128_t x);
/*
* Find the nth prime using a combination of the prime counting
* function and the sieve of Eratosthenes.
*
* @pre n <= 216289611853439384
* @return -1 if an error occurs, else the nth prime.
*
* Run time: O(x^(2/3) / (log x)^2)
* Memory usage: O(x^(1/3) * (log x)^3)
*/
int64_t primecount_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.
* @return -1 if an error occurs, else the nth prime.
*
* Run time: O(x^(2/3) / (log x)^2)
* Memory usage: O(x^(1/3) * (log x)^3)
*/
pc_int128_t primecount_nth_prime_128(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.
* @return -1 if an error occurs.
*/
int64_t primecount_phi(int64_t x, int64_t a);
/* Get the currently set number of threads */
int primecount_get_num_threads(void);
/* Set the number of threads */
void primecount_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 primecount_set_double_check(bool enable);
/* Get the primecount version number, in the form āi.jā */
const char* primecount_version(void);
#ifdef __cplusplus
} /* extern "C" */
#endif
#endif
|
