aboutsummaryrefslogtreecommitdiff
path: root/src/commands/factor.js
diff options
context:
space:
mode:
authorSoccera1 <[email protected]>2026-07-18 09:27:17 +1000
committerSoccera1 <[email protected]>2026-07-18 09:27:17 +1000
commit6f5241afb5bd1d6a1a8724bf06cc6f205c279402 (patch)
tree2aa852e968f6b89f2c8458333ce3e7c38b3c2450 /src/commands/factor.js
parenta753f669c9bedfccb9f7f400da018bb487dca5d0 (diff)
downloadbnu-6f5241afb5bd1d6a1a8724bf06cc6f205c279402.tar.gz
bnu-6f5241afb5bd1d6a1a8724bf06cc6f205c279402.zip
Refactor to single call
Diffstat (limited to 'src/commands/factor.js')
-rw-r--r--src/commands/factor.js660
1 files changed, 660 insertions, 0 deletions
diff --git a/src/commands/factor.js b/src/commands/factor.js
new file mode 100644
index 0000000..db0110f
--- /dev/null
+++ b/src/commands/factor.js
@@ -0,0 +1,660 @@
+#!/usr/bin/env bun
+
+import { fstatSync, readSync } from "node:fs";
+import { cpus } from "node:os";
+import { decodeSurrogateEscapedBytes, isWriteError, localeQuotedDiagnostic, lsEscapedName, parseOptions, readAll, systemErrorMessage } from "../shared/common.js";
+import { fail, stderr, stdout } from "../shared/diagnostics.js";
+import { defineCommand, runAsMain } from "../shared/command.js";
+
+export const FACTOR_LONG_OPTIONS = ["exponents", "help", "version"];
+
+export function factorMetaOption(args) {
+ for (const arg of args) {
+ if (arg === "--") return null;
+ if (!arg.startsWith("-") || arg === "-") continue;
+ if (arg.startsWith("--")) {
+ const option = normalizeFactorLongOption(arg);
+ const name = option.slice(2).split("=", 1)[0];
+ if (!FACTOR_LONG_OPTIONS.includes(name) || option.includes("=")) return null;
+ if (option === "--help" || option === "--version") return option;
+ continue;
+ }
+ for (let j = 1; j < arg.length; j++) if (arg[j] !== "h") return null;
+ }
+ return null;
+}
+
+export function factorize(value) {
+ let n = BigInt(value);
+ if (n < 0n) n = -n;
+ if (n <= 1n) return [];
+ const factors = [];
+ for (const d of [2n, 3n, 5n, 7n, 11n, 13n, 17n, 19n, 23n, 29n, 31n]) {
+ while (n % d === 0n) {
+ factors.push(d);
+ n /= d;
+ }
+ }
+ if (n > 1n) factorBigInt(n, factors);
+ return factors.sort((a, b) => a < b ? -1 : a > b ? 1 : 0);
+}
+
+export function factorBigInt(n, factors) {
+ if (n === 1n) return;
+ if (isProbablePrime(n)) {
+ factors.push(n);
+ return;
+ }
+ const nearDouble = factorNearDoubleSemiprime(n);
+ if (nearDouble != null) {
+ factorBigInt(nearDouble, factors);
+ factorBigInt(n / nearDouble, factors);
+ return;
+ }
+ // A high-bound p-1 pass is useful for very large residuals with smooth
+ // predecessor factors, but it is disproportionately expensive across a
+ // contiguous range of 96-bit values. Pollard rho is the better first
+ // strategy below this threshold.
+ const pMinusOne = n >= 1_000_000_000_000_000_000_000_000_000_000n
+ ? pollardPMinusOne(n, 500_000)
+ : n >= (1n << 72n)
+ ? pollardPMinusOne(n, 100_000)
+ : null;
+ if (pMinusOne != null) {
+ factorBigInt(pMinusOne, factors);
+ factorBigInt(n / pMinusOne, factors);
+ return;
+ }
+ const divisor = pollardRho(n);
+ factorBigInt(divisor, factors);
+ factorBigInt(n / divisor, factors);
+}
+
+export function bigintGcd(a, b) {
+ while (b !== 0n) {
+ const t = a % b;
+ a = b;
+ b = t;
+ }
+ return a < 0n ? -a : a;
+}
+
+export function modPow(base, exponent, mod) {
+ let result = 1n;
+ base %= mod;
+ while (exponent > 0n) {
+ if (exponent & 1n) result = (result * base) % mod;
+ base = (base * base) % mod;
+ exponent >>= 1n;
+ }
+ return result;
+}
+
+export function factorNearDoubleSemiprime(n) {
+ if (n < 1_000_000_000_000_000_000n) return null;
+ for (let delta = -4096n; delta <= 4096n; delta++) {
+ const discriminant = delta * delta + 8n * n;
+ const root = bigintSqrt(discriminant);
+ if (root * root !== discriminant) continue;
+ const numerator = root - delta;
+ if (numerator % 4n !== 0n) continue;
+ const factor = numerator / 4n;
+ if (factor > 1n && factor < n && n % factor === 0n) return factor;
+ }
+ return null;
+}
+
+export function pollardPMinusOne(n, bound) {
+ let a = 2n;
+ let sinceGcd = 0;
+ for (const p of primesUpTo(bound)) {
+ let power = p;
+ while (power <= Math.floor(bound / p)) power *= p;
+ a = modPow(a, BigInt(power), n);
+ if (++sinceGcd < 256) continue;
+ sinceGcd = 0;
+ const d = bigintGcd(a - 1n, n);
+ if (d > 1n && d < n) return d;
+ if (d === n) return null;
+ }
+ const d = bigintGcd(a - 1n, n);
+ return d > 1n && d < n ? d : null;
+}
+
+export function bigintSqrt(n) {
+ if (n < 2n) return n;
+ let x = 1n << BigInt(Math.ceil(n.toString(2).length / 2));
+ for (;;) {
+ const y = (x + n / x) >> 1n;
+ if (y >= x) return x;
+ x = y;
+ }
+}
+
+export function isProbablePrime(n) {
+ if (n < 2n) return false;
+ for (const p of [2n, 3n, 5n, 7n, 11n, 13n, 17n, 19n, 23n, 29n, 31n, 37n]) {
+ if (n === p) return true;
+ if (n % p === 0n) return false;
+ }
+ let d = n - 1n;
+ let s = 0n;
+ while ((d & 1n) === 0n) {
+ d >>= 1n;
+ s++;
+ }
+ const bases = n < (1n << 128n) ? [2n, 3n, 5n, 7n, 11n, 13n, 17n] : [2n, 3n, 5n, 7n, 11n, 13n, 17n, 19n, 23n, 29n, 31n, 37n];
+ for (const a of bases) {
+ if (a >= n - 2n) continue;
+ let x = modPow(a, d, n);
+ if (x === 1n || x === n - 1n) continue;
+ let composite = true;
+ for (let r = 1n; r < s; r++) {
+ x = (x * x) % n;
+ if (x === n - 1n) {
+ composite = false;
+ break;
+ }
+ }
+ if (composite) return false;
+ }
+ return true;
+}
+
+export function pollardRho(n) {
+ if (n % 2n === 0n) return 2n;
+ const preferredConstants = [13n, 3n, 1n, 22n, 11n, 4n, 15n, 5n, 7n, 2n, 17n, 19n, 26n];
+ for (let attempt = 0; ; attempt++) {
+ const c = attempt < preferredConstants.length ? preferredConstants[attempt] : BigInt(attempt + 1);
+ let y = 2n;
+ let d = 1n;
+ let r = 1;
+ let q = 1n;
+ let x = 0n;
+ let ys = 0n;
+ const f = (v) => (v * v + c) % n;
+ while (d === 1n) {
+ x = y;
+ for (let i = 0; i < r; i++) y = f(y);
+ let k = 0;
+ while (k < r && d === 1n) {
+ ys = y;
+ const limit = Math.min(256, r - k);
+ for (let i = 0; i < limit; i++) {
+ y = f(y);
+ const diff = x > y ? x - y : y - x;
+ q = (q * diff) % n;
+ }
+ d = bigintGcd(q, n);
+ k += 256;
+ }
+ r *= 2;
+ if (r > 2_000_000 && d === 1n) break;
+ }
+ if (d === n) {
+ do {
+ ys = f(ys);
+ d = bigintGcd(x > ys ? x - ys : ys - x, n);
+ } while (d === 1n);
+ }
+ if (d > 1n && d < n) return d;
+ if (attempt === preferredConstants.length - 1 && n > 1_000_000_000_000_000_000_000_000n) {
+ const pPlusOne = pollardPPlusOne(n, 11_000_000, 6n);
+ if (pPlusOne != null) return pPlusOne;
+ }
+ }
+}
+
+export function pollardPPlusOne(n, bound, parameter) {
+ let v = parameter;
+ for (const p of primesUpTo(bound)) {
+ let power = p;
+ while (power <= Math.floor(bound / p)) power *= p;
+ v = lucasV(v, BigInt(power), n);
+ }
+ const d = bigintGcd(v - 2n, n);
+ return d > 1n && d < n ? d : null;
+}
+
+export function lucasV(parameter, exponent, mod) {
+ let vk = 2n % mod;
+ let vk1 = parameter % mod;
+ for (const bit of exponent.toString(2)) {
+ const v2k = positiveMod(vk * vk - 2n, mod);
+ const v2k1 = positiveMod(vk * vk1 - parameter, mod);
+ if (bit === "0") {
+ vk = v2k;
+ vk1 = v2k1;
+ } else {
+ vk = v2k1;
+ vk1 = positiveMod(vk1 * vk1 - 2n, mod);
+ }
+ }
+ return vk;
+}
+
+export function positiveMod(value, mod) {
+ value %= mod;
+ return value < 0n ? value + mod : value;
+}
+
+export async function factor(args) {
+ args = normalizeFactorLongOptions(args);
+ const { opts, operands } = parseOptions(args, { short: { h: false }, long: { exponents: false, help: false, version: false } });
+ opts.exponents = opts.h || opts.exponents;
+ if (!operands.length && !fstatSync(0).isFile()) return streamFactorStdin(opts);
+ let values;
+ try {
+ if (operands.length) values = operands.map((operand) => String(operand).replace(/\0\S*/g, ""));
+ else {
+ const input = decodeSurrogateEscapedBytes(await readAll("-"));
+ const fastStatus = factorFastSmallIntegerInput(input, opts);
+ if (fastStatus != null) return fastStatus;
+ values = input.replace(/\0\S*/g, "").trim().split(/\s+/).filter(Boolean);
+ }
+ } catch (error) {
+ return fail("factor", `error reading input: ${systemErrorMessage(error)}`);
+ }
+ const parallel = await factorLargeContiguousRangeInParallel(values, opts);
+ if (parallel != null) return parallel;
+ const batchFactors = prepareSmallIntegerFactorizer(values) ?? prepareContiguousRangeFactorizer(values);
+ let status = 0;
+ for (const raw of values) {
+ status = factorOneValue(raw, opts, batchFactors) || status;
+ }
+ return status;
+}
+
+export async function streamFactorStdin(opts) {
+ let pending = [];
+ let pendingLength = 0;
+ let values = [];
+ let status = 0;
+ const flushValues = async () => {
+ if (!values.length) return;
+ const batch = values;
+ values = [];
+ const parallelStatus = await factorLargeContiguousRangeInParallel(batch, opts);
+ if (parallelStatus != null) {
+ status = parallelStatus || status;
+ return;
+ }
+ // Dense small ranges (notably upstream factor/t00: 0..10,000,000)
+ // must use the compact Uint32 sieve. The generic range factorizer keeps
+ // one JS array per value and caused JSC heap growth into multiple GiB.
+ const batchFactors = prepareSegmentedSmallIntegerFactorizer(batch)
+ ?? prepareSmallIntegerFactorizer(batch)
+ ?? prepareContiguousRangeFactorizer(batch);
+ for (const raw of batch) status = factorOneValue(raw, opts, batchFactors) || status;
+ };
+ const flushToken = () => {
+ if (!pendingLength) return;
+ const raw = decodeSurrogateEscapedBytes(Buffer.concat(pending, pendingLength)).replace(/\0\S*/g, "");
+ pending = [];
+ pendingLength = 0;
+ if (raw) values.push(raw);
+ };
+ try {
+ const inputBuffer = Buffer.allocUnsafe(64 * 1024);
+ while (true) {
+ const bytesRead = readSync(0, inputBuffer, 0, inputBuffer.length, null);
+ if (bytesRead === 0) break;
+ const chunk = inputBuffer.subarray(0, bytesRead);
+ let start = 0;
+ for (let index = 0; index < chunk.length; index++) {
+ if (![9, 10, 11, 12, 13, 32].includes(chunk[index])) continue;
+ if (index > start) {
+ const part = Buffer.from(chunk.subarray(start, index));
+ pending.push(part);
+ pendingLength += part.length;
+ }
+ flushToken();
+ start = index + 1;
+ }
+ if (start < chunk.length) {
+ const part = Buffer.from(chunk.subarray(start));
+ pending.push(part);
+ pendingLength += part.length;
+ }
+ // Process four 100k-value child chunks concurrently while applying
+ // backpressure to stdin, keeping the range optimization bounded.
+ if (values.length >= 400_000) await flushValues();
+ }
+ flushToken();
+ await flushValues();
+ return status;
+ } catch (error) {
+ if (isWriteError(error)) throw error;
+ return fail("factor", `error reading input: ${systemErrorMessage(error)}`);
+ }
+}
+
+export function factorOneValue(raw, opts, batchFactors = null) {
+ const value = raw.replace(/^\+/, "");
+ if (!/^\d+$/.test(value)) {
+ stderr(`factor: ${localeQuotedDiagnostic(factorDiagnosticValue(raw))} is not a valid positive integer\n`);
+ return 1;
+ }
+ const normalizedValue = normalizeFactorValue(value);
+ const factors = batchFactors?.get(normalizedValue) ?? factorize(normalizedValue);
+ stdout(`${normalizedValue}:${formatFactors(factors, opts).map((n) => ` ${n}`).join("")}\n`);
+ return 0;
+}
+
+export const FACTOR_FAST_OUTPUT_CHUNK_BYTES = 4096;
+
+export function factorFastSmallIntegerInput(input, opts) {
+ if (opts.exponents || input.includes("\0")) return null;
+ let count = 0;
+ let max = 0;
+ for (const token of input.matchAll(/\S+/g)) {
+ const raw = token[0];
+ const value = raw.replace(/^\+/, "");
+ if (!/^\d+$/.test(value) || value.length > 8) return null;
+ const n = Number(value);
+ if (!Number.isSafeInteger(n)) return null;
+ if (n > max) max = n;
+ count++;
+ }
+ if (count < 10000 || max > 100_000_000) return null;
+
+ const spf = smallestPrimeFactors(max);
+ let out = "";
+ for (const token of input.matchAll(/\S+/g)) {
+ const n = Number(token[0].replace(/^\+/, ""));
+ const line = `${n}:${formatSmallIntegerFactors(n, spf)}\n`;
+ if (out && out.length + line.length > FACTOR_FAST_OUTPUT_CHUNK_BYTES) {
+ stdout(out);
+ out = "";
+ }
+ out += line;
+ }
+ if (out) stdout(out);
+ return 0;
+}
+
+export function formatSmallIntegerFactors(value, spf) {
+ if (value <= 1) return "";
+ let n = value;
+ let out = "";
+ while (n > 1) {
+ const p = spf[n] || n;
+ out += ` ${p}`;
+ n = Math.trunc(n / p);
+ }
+ return out;
+}
+
+export function factorDiagnosticValue(value) {
+ return [...String(value)].map((ch) => {
+ if (/[\udc80-\udcff]/.test(ch)) return `\\${(ch.charCodeAt(0) - 0xdc00).toString(8).padStart(3, "0")}`;
+ return lsEscapedName(ch, { escapeDouble: false });
+ }).join("");
+}
+
+export function normalizeFactorValue(value) {
+ return BigInt(value).toString();
+}
+
+export function normalizeFactorLongOptions(args) {
+ const out = [];
+ let end = false;
+ for (const arg of args) {
+ if (end || arg === "--" || !arg.startsWith("--")) {
+ out.push(arg);
+ if (arg === "--") end = true;
+ continue;
+ }
+ out.push(normalizeFactorLongOption(arg));
+ }
+ return out;
+}
+
+export function normalizeFactorLongOption(arg) {
+ const body = arg.slice(2);
+ const eq = body.indexOf("=");
+ const name = eq === -1 ? body : body.slice(0, eq);
+ if (!name) return arg;
+ const match = FACTOR_LONG_OPTIONS.find((option) => option.startsWith(name));
+ if (!match) return arg;
+ return eq === -1 ? `--${match}` : `--${match}=${body.slice(eq + 1)}`;
+}
+
+export async function factorLargeContiguousRangeInParallel(values, opts) {
+ if (process.env.BNU_FACTOR_CHILD === "1" || values.length < 2000 || opts.exponents) return null;
+ const normalized = [];
+ for (const raw of values) {
+ const value = raw.replace(/^\+/, "");
+ if (!/^\d+$/.test(value)) return null;
+ normalized.push(value);
+ }
+ const lo = BigInt(normalized[0]);
+ const hi = BigInt(normalized[normalized.length - 1]);
+ if (lo < 1_000_000_000_000_000_000n || hi < lo || hi - lo !== BigInt(normalized.length - 1)) return null;
+ for (let i = 1; i < normalized.length; i++) {
+ if (BigInt(normalized[i]) !== lo + BigInt(i)) return null;
+ }
+
+ // Each Bun worker carries a substantial runtime and JIT footprint. Keep
+ // the default single-process so an ordinary invocation cannot multiply its
+ // memory use by the host CPU count. Controlled benchmarks and audits may
+ // opt in to bounded parallelism with BNU_FACTOR_WORKERS.
+ const configuredWorkerLimit = /^\d+$/.test(process.env.BNU_FACTOR_WORKERS ?? "")
+ ? Number(process.env.BNU_FACTOR_WORKERS)
+ : null;
+ const workerLimit = configuredWorkerLimit ?? 1;
+ const workers = Math.min(workerLimit, Math.max(1, Math.floor(values.length / 100)), cpus().length || 1);
+ if (workers < 2) return null;
+ const chunkSize = Math.ceil(values.length / workers);
+ const chunks = [];
+ for (let i = 0; i < values.length; i += chunkSize) chunks.push(values.slice(i, i + chunkSize));
+ const results = await Promise.all(chunks.map(async (chunk) => {
+ const proc = Bun.spawn([process.execPath, import.meta.path, "factor"], {
+ env: { ...process.env, BNU_FACTOR_CHILD: "1" },
+ stdin: new Blob([chunk.join("\n") + "\n"]),
+ stdout: "pipe",
+ stderr: "pipe",
+ });
+ const [code, out, err] = await Promise.all([
+ proc.exited,
+ new Response(proc.stdout).text(),
+ new Response(proc.stderr).text(),
+ ]);
+ return { code, out, err };
+ }));
+ let status = 0;
+ for (const result of results) {
+ if (result.out) stdout(result.out);
+ if (result.err) stderr(result.err);
+ if (result.code !== 0) status = result.code;
+ }
+ return status;
+}
+
+export function prepareContiguousRangeFactorizer(values) {
+ if (values.length < 100 || values.length > 1_000_000) return null;
+ const normalized = [];
+ for (const raw of values) {
+ const value = raw.replace(/^\+/, "");
+ if (!/^\d+$/.test(value)) return null;
+ normalized.push(value);
+ }
+ const lo = BigInt(normalized[0]);
+ const hi = BigInt(normalized[normalized.length - 1]);
+ if (hi < lo || hi - lo !== BigInt(normalized.length - 1)) return null;
+ for (let i = 1; i < normalized.length; i++) {
+ if (BigInt(normalized[i]) !== lo + BigInt(i)) return null;
+ }
+
+ const residues = normalized.map(BigInt);
+ const factors = Array.from({ length: normalized.length }, () => []);
+ for (const p of primesUpTo(1_000_000)) {
+ const bigP = BigInt(p);
+ const rem = lo % bigP;
+ let index = Number(rem === 0n ? 0n : bigP - rem);
+ for (; index < residues.length; index += p) {
+ while (residues[index] % bigP === 0n) {
+ factors[index].push(bigP);
+ residues[index] /= bigP;
+ }
+ }
+ }
+
+ return {
+ get(value) {
+ const index = Number(BigInt(value) - lo);
+ if (index < 0 || index >= residues.length) return null;
+ const out = [...factors[index]];
+ if (residues[index] > 1n) out.push(...factorize(residues[index]));
+ return out.sort((a, b) => a < b ? -1 : a > b ? 1 : 0);
+ },
+ };
+}
+
+export const primeCache = new Map();
+
+export function primesUpTo(max) {
+ const cached = primeCache.get(max);
+ if (cached) return cached;
+ const composite = new Uint8Array(max + 1);
+ const primes = [];
+ for (let i = 2; i <= max; i++) {
+ if (composite[i]) continue;
+ primes.push(i);
+ if (i > Math.floor(max / i)) continue;
+ for (let j = i * i; j <= max; j += i) composite[j] = 1;
+ }
+ primeCache.set(max, primes);
+ return primes;
+}
+
+export function prepareSmallIntegerFactorizer(values) {
+ if (values.length < 10000) return null;
+ let max = 0;
+ for (const raw of values) {
+ const value = raw.replace(/^\+/, "");
+ if (!/^\d+$/.test(value) || value.length > 8) return null;
+ const n = Number(value);
+ if (!Number.isSafeInteger(n)) return null;
+ if (n > max) max = n;
+ }
+ if (max > 100_000_000) return null;
+ const spf = smallestPrimeFactors(max);
+ return {
+ get(value) {
+ let n = Number(value);
+ if (n <= 1) return [];
+ const factors = [];
+ while (n > 1) {
+ const p = spf[n] || n;
+ factors.push(BigInt(p));
+ n = Math.trunc(n / p);
+ }
+ return factors;
+ },
+ };
+}
+
+export function prepareSegmentedSmallIntegerFactorizer(values) {
+ if (values.length < 10_000) return null;
+ const normalized = [];
+ for (const raw of values) {
+ const value = raw.replace(/^\+/, "");
+ if (!/^\d+$/.test(value) || value.length > 8) return null;
+ const n = Number(value);
+ if (!Number.isSafeInteger(n) || n > 100_000_000) return null;
+ normalized.push(n);
+ }
+ const lo = normalized[0];
+ const hi = normalized.at(-1);
+ if (hi - lo !== normalized.length - 1) return null;
+ for (let index = 1; index < normalized.length; index++) {
+ if (normalized[index] !== lo + index) return null;
+ }
+
+ // Keep a compact CSR-style table of every factor in this segment. Storing
+ // only the first divisor forced each residual through the generic Pollard
+ // path and made the 80m..90m upstream range take more than 15 minutes.
+ // Two sieve passes cost little and keep a 400k-value batch to a few typed
+ // arrays rather than one JS array per integer.
+ const primes = primesUpTo(Math.floor(Math.sqrt(hi)));
+ const residues = new Uint32Array(normalized);
+ const counts = new Uint8Array(normalized.length);
+ for (const p of primes) {
+ let first = Math.ceil(lo / p) * p;
+ if (first < p * p) first = p * p;
+ for (let value = first; value <= hi; value += p) {
+ const index = value - lo;
+ while (residues[index] > 1 && residues[index] % p === 0) {
+ residues[index] = Math.trunc(residues[index] / p);
+ counts[index]++;
+ }
+ }
+ }
+ for (let index = 0; index < residues.length; index++) {
+ if (residues[index] > 1) counts[index]++;
+ }
+ const offsets = new Uint32Array(normalized.length + 1);
+ for (let index = 0; index < counts.length; index++) offsets[index + 1] = offsets[index] + counts[index];
+ const factors = new Uint32Array(offsets.at(-1));
+ const positions = new Uint32Array(offsets.subarray(0, normalized.length));
+ residues.set(normalized);
+ for (const p of primes) {
+ let first = Math.ceil(lo / p) * p;
+ if (first < p * p) first = p * p;
+ for (let value = first; value <= hi; value += p) {
+ const index = value - lo;
+ while (residues[index] > 1 && residues[index] % p === 0) {
+ residues[index] = Math.trunc(residues[index] / p);
+ factors[positions[index]++] = p;
+ }
+ }
+ }
+ for (let index = 0; index < residues.length; index++) {
+ if (residues[index] > 1) factors[positions[index]++] = residues[index];
+ }
+ return {
+ get(value) {
+ const original = Number(value);
+ const index = original - lo;
+ if (index < 0 || index >= normalized.length || original <= 1) return original <= 1 ? [] : null;
+ const out = [];
+ for (let position = offsets[index]; position < offsets[index + 1]; position++) out.push(BigInt(factors[position]));
+ return out;
+ },
+ };
+}
+
+export let smallestPrimeFactorCache = new Uint32Array(0);
+
+export function smallestPrimeFactors(max) {
+ if (smallestPrimeFactorCache.length > max) return smallestPrimeFactorCache;
+ const spf = new Uint32Array(max + 1);
+ for (let i = 2; i <= max; i++) {
+ if (spf[i] !== 0) continue;
+ spf[i] = i;
+ if (i > Math.floor(max / i)) continue;
+ for (let j = i * i; j <= max; j += i) {
+ if (spf[j] === 0) spf[j] = i;
+ }
+ }
+ smallestPrimeFactorCache = spf;
+ return spf;
+}
+
+export function formatFactors(factors, opts) {
+ if (!opts.exponents) return factors.map(String);
+ const out = [];
+ for (let i = 0; i < factors.length;) {
+ let count = 1;
+ while (factors[i + count] === factors[i]) count++;
+ out.push(count === 1 ? String(factors[i]) : `${factors[i]}^${count}`);
+ i += count;
+ }
+ return out;
+}
+
+const singleCall = defineCommand("factor", factor, factorMetaOption);
+export default singleCall;
+
+if (import.meta.main) await runAsMain(singleCall);