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

#[link(name = "primecount", kind = "static")]
extern "C" {
    fn primecount_pi(x: i64) -> i64;
    fn primecount_phi(x: i64, a: i64) -> i64;
    fn primecount_nth_prime(n: i64) -> i64;
}

/// Counts the number of primes <= `x` using Xavier Gourdon's
/// algorithm. Uses all CPU cores by default.
///
/// Returns -1 if an error occurs.
///
/// # Examples
///
/// ```
/// // The primes are: 2, 3, 5 and 7.
/// assert_eq!(primecount::pi(10), 4);
///
/// // The primes are: 2, 3, 5, 7 and 11.
/// assert_eq!(primecount::pi(11), 5);
///
/// assert_eq!(primecount::pi(10i64.pow(12)), 37607912018);
/// ```
///
/// - Run time complexity: O(x^(2/3) / (log x)^2)
/// - Memory usage: O(x^(1/3) * (log x)^3)
pub fn pi(x: i64) -> i64 {
    unsafe { primecount_pi(x) }
}

/// 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.
///
/// Returns -1 if an error occurs.
///
/// # Examples
///
/// ```
/// // The numbers are: 1, 5 and 7.
/// assert_eq!(primecount::phi(10, 2), 3);
///
/// // The numbers are: 1, 7, 11 and 13.
/// assert_eq!(primecount::phi(15, 3), 4);
///
/// assert_eq!(primecount::phi(10i64.pow(12), 78498i64), 37607833521)
/// ```
pub fn phi(x: i64, a: i64) -> i64 {
    unsafe { primecount_phi(x, a) }
}

/// Find the `n`th prime using a combination of the prime counting
/// function and the sieve of Eratosthenes.
///
/// @pre n <= 216289611853439384
///
/// Returns -1 if an error occurs.
///
/// # Examples
///
/// ```
/// assert_eq!(primecount::nth_prime(1), 2);
/// assert_eq!(primecount::nth_prime(5), 11);
/// assert_eq!(primecount::nth_prime(455052511), 9999999967);
/// ```
///
/// - Run time: O(x^(2/3) / (log x)^2)
/// - Memory usage: O(x^(1/2))
pub fn nth_prime(n: i64) -> i64 {
    unsafe { primecount_nth_prime(n) }
}

// TODO(madiyar): Add i128 version of APIs.