Baseline Bit Manipulation · Advanced Maths O(sqrt(n)) for the trial sweep; the sieve array makes it O(n log log n) as written · O(n) for the sieve flags
A foundry receives an alloy batch identified by an integer and must list every base-metal unit that composes it — prime factors with multiplicity, so a doubled component appears twice. The factor-sieve marks shared-access values as it goes, and every surviving prime is divided out of the batch repeatedly, one entry per removal, until nothing but 1 remains.
Input: An integer n greater than 1.
Output: The prime factors of n with multiplicity, in non-decreasing order.
2 <= n <= 10^9Input: {"n":12246}
Output: [2,3,13,157]
12246 = 2 * 3 * 13 * 157 — four single-power components.
Input: {"n":12}
Output: [2,2,3]
The 2-component occurs squared, so it is listed twice.