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;
}