https://coins.github.io/primes-js/src/prime-counting/prime-counting.js

1import { primesList as Primes } from '../primes/primes-list.js';
2
3/**
4 *
5 *    A fast prime-counting algorithm.
6 *    It counts the number of primes up to n.
7 *     It is a variant of the Meissel-Lehmer Algorithm.
8 *    
9 */
10const MAX_PRIME = Primes[Primes.length - 1]; // The largest prime in our database
11const MAX_N = MAX_PRIME * MAX_PRIME; // Our database enables us to count up to this number
12
13
14
15/**
16 *
17 * Counts the number of prime less than or equal to some number.
18 * @param {number} n The number
19 * @return {number} The number of primes up to n
20 *
21 */
22export function countPrimes(n) {
23    if (n < 2) return 0;
24    if (n === 2) return 1;
25    if (n === 3) return 2;
26    if (n > MAX_N) throw Error('N is too big. Bigger database of primes required!')
27
28    let countPrimes = n; // We assume all numbers are prime and then we subtract the composites
29    let index = 0;
30    let p = Primes[0];
31
32    while (p * p <= n) { // We iterate over all primes up to sqrt(n)
33        const m = Math.floor(n / p); // FIXME: this integer division could be done faster
34        countPrimes -= countAlmostPrimesCached(m, p, index); // subtract all composites which's smallest factor is p
35
36        index++;
37        p = Primes[index];
38    }
39    return countPrimes
40}
41
42
43
44/* 
45    
46    Counts the number of "p-almost-primes" up to m and caches the result.
47    
48    A number is "p-almost-prime", if it has no factors smaller than p 
49    
50*/
51
52const cache2 = {}
53
54function countAlmostPrimesCached(m, p, index) {
55    // We know these results without computation:
56    if (p === 2) return m; // All numbers are 2-almost-primes
57    if (m === 0) return -1; // FIXME: where are these artifacts coming from??
58    if (m < p) return 0; // No number has a factor bigger than itself
59    if (m === p || m - 1 === p) return 1; // There is only one number with a factor as big as itself (or one less)
60
61    if (p * p > m) { // This means, all "p-almost-primes" up to m are actually primes
62        // So let's count only the primes
63
64        if (m > MAX_PRIME) return countPrimes(m) - index; // m is still too large. Let's recurse
65
66        // Yey, we can calculate countPrimes(m) "by hand"!
67        let countPrimes_m = index;
68        while (Primes[countPrimes_m] <= m) countPrimes_m++; // FIXME: Binary search here 
69        return countPrimes_m - index;
70    }
71
72
73    // Otherwise, there's actually work to do. Let's cache it
74    const cacheKey = m + '_' + p;
75    if (!cache2[cacheKey])
76        cache2[cacheKey] = _countAlmostPrimes(m, p);
77    return cache2[cacheKey];
78}
79
80function _countAlmostPrimes(m, p) {
81    let index = 0;
82    let q = Primes[0];
83
84    let almostPrimes = m; // Assume all numbers are p-almost-prime and then substract the rest
85    while (q < p) { // We iterate over all primes smaller than p
86        const m1 = Math.floor(m / q); // FIXME: this integer division could be done faster
87        almostPrimes -= countAlmostPrimesCached(m1, q, index);
88
89        index++;
90        q = Primes[index];
91    }
92    almostPrimes = almostPrimes - index;
93    return almostPrimes
94}
95
96
97
98
99
100// /*
101
102//     Benchmarks and Tests
103
104// */
105// function benchmark(n, actualValue) {
106//     const start = Date.now();
107//     const counted = countPrimes(10 ** n)
108//     if (counted !== actualValue) throw Error('miscounted!!!')
109//     console.log(`Primes up to 10^${n}: ${counted} time=${Date.now()-start}ms`);
110// }
111
112// console.log('Prime Counting Benchmark started...')
113// // benchmark(2, 25)
114// // benchmark(3, 168)
115// // benchmark(4, 1229)
116// // benchmark(5, 9592)
117// // benchmark(6, 78498)
118// // benchmark(7, 664579)
119// benchmark(8, 5761455)
120// // benchmark(9, 50847534)
121// // benchmark(10, 455052511)
122// // benchmark(11, 4118054813)