primecount 0.2.1

Rust wrapper for https://github.com/kimwalisch/primecount
Documentation 
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

///
/// @file  pi_legendre.cpp
/// @brief Count the number of primes <= x using Legendre's formula.
///        Legendre's prime counting algorithm is the simplest
///        combinatorial algorithm for counting the number of primes.
///        All other formulas (e.g. Meissel's formula, Lehmer's
///        formula, ...) are extensions of Legendre's formula that
///        run faster but are also more complex.
///
///        Legendre's formula:
///        pi(x) = pi(y) + phi(x, pi(y)) - 1
///        with y = x^(1/2)
///
/// Copyright (C) 2021 Kim Walisch, <kim.walisch@gmail.com>
///
/// This file is distributed under the BSD License. See the COPYING
/// file in the top level directory.
///

#include <primecount-internal.hpp>
#include <print.hpp>
#include <isqrt.hpp>

#include <stdint.h>

namespace primecount {

/// Count the number of primes <= x using Legendre's formula.
/// Run time: O(x)
/// Memory usage: O(x^(1/2))
///
int64_t pi_legendre(int64_t x,
                    int threads,
                    bool is_print)
{
  if (x < 2)
    return 0;

  int64_t y = isqrt(x);
  int64_t a = pi_noprint(y, threads);

  if (is_print)
  {
    print("");
    print("=== pi_legendre(x) ===");
    print("pi(x) = phi(x, a) + a - 1");
    print("x", x);
    print("a", a);
    print("threads", threads);
  }

  int64_t phi_xa = phi(x, a, threads, is_print);
  int64_t sum = phi_xa + a - 1;

  return sum;
}

} // namespace