src/sieve/eratosthenes23.js

import {ptoi23} from './ptoi23.js';
import {ptoi230} from './ptoi230.js';
import {ptoi231} from './ptoi231.js';
import {itop23} from './itop23.js';
import {itop230} from './itop230.js';
import {itop231} from './itop231.js';
 
/**
 * Sieve of Eratosthenes skipping all multiples of 2 and 3.
 *
 * 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79
 * 0 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
 *
 * 83 85 89 91 95 97 101 103 107 109 113 115 119 121 125 127 131 133 137 139
 * 26 27 28 29 30 31  32  33  34  35  36  37  38  39  40  41  42  43  44  45
 *
 * 143 145 149 151 155 157 161 163 167 169 173 175 179 181 185 187 191
 *  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62
 *
 *
 *
 * i( 5) = 0
 * i(25) = 7
 * i(35) = 10 = 7 + 5 - 2
 *
 * i( 7) = 1
 * i(49) = 15
 * i(77) = 24 = 15 + 7 + 2
 *
 * i( 11) = 2
 * i(121) = 39
 * i(143) = 46 = 39 + 11 - 4
 *
 * i( 13) = 3
 * i(139) = 45
 * i(191) = 62 = 45 + 13 + 4
 */
 
export function __eratosthenes23__(alloc, fill, get, gothrough, usqrt) {
	const first = 5;
 
	const eratosthenes23 = function (n, callback) {
		let j;
		let p;
		let l;
 
		if (n <= 2) {
			return null;
		}
 
		callback(2);
 
		if (n <= 3) {
			return null;
		}
 
		callback(3);
 
		if (n <= 5) {
			return null;
		}
 
		const size = ptoi23(n);
 
		const sieve = alloc(size);
		fill(sieve, 0, size, true);
 
		const m = ptoi23(usqrt(n));
		let i = ptoi230(first);
 
		for (l = 2; ; l += 2) {
			if (i >= m) {
				break;
			}
 
			if (get(sieve, i)) {
				p = itop230(i);
 
				callback(p);
 
				j = ptoi231(p * p);
 
				gothrough(sieve, j, size, 2 * p);
				gothrough(sieve, j + p - l, size, 2 * p);
			}
 
			++i;
 
			if (i >= m) {
				break;
			}
 
			if (get(sieve, i)) {
				p = itop231(i);
 
				callback(p);
 
				j = ptoi231(p * p);
 
				gothrough(sieve, j, size, 2 * p);
				gothrough(sieve, j + p + l, size, 2 * p);
			}
 
			++i;
		}
 
		i = m;
 
		for (;;) {
			if (i >= size) {
				break;
			}
 
			if (get(sieve, i)) {
				callback(itop23(i));
			}
 
			++i;
 
			if (i >= size) {
				break;
			}
 
			if (get(sieve, i)) {
				callback(itop23(i));
			}
 
			++i;
		}
 
		return sieve;
	};
 
	return eratosthenes23;
}