Prime Factor & Divisor Tree

Factorising by trial division costs about the square root of N. Doing it with a smallest-prime-factor sieve costs about the number of prime factors, which is under 24 for any 64-bit number. The Prime Factorizer builds that sieve once for everything up to 100,000 and falls back to trial division above it.

Four cards answer the questions a factorisation is usually a step towards: whether N is prime, how many divisors it has, Euler's totient, and how many distinct prime factors there are. Below them the full sorted divisor list is laid out with the prime ones tinted green.

Eight example chips run from 1 through 360 and 99,991 to 1,000,000, which between them cover the degenerate case, a highly composite number, a 5-digit prime and a perfect power. Everything computes on the page.

A Real Example: Factoring 360

The field opens on 360. The factorisation line reads 360 = 2^3 × 3^2 × 5, and the cards report 24 divisors, an Euler totient of 96, and 3 distinct prime factors. Those numbers are related: multiply each exponent plus one, 4 times 3 times 2, and you get the divisor count without listing anything. The totient comes from the same factorisation, multiplying 360 by one half, two thirds and four fifths.

The Algorithm: Smallest Prime Factor Sieve

• The sieve stores, for every value up to 100,000, the smallest prime that divides it. Factorising is then a loop that divides out that prime and looks up the quotient, with no search at all.
• It is built once when the module loads, so the cost is paid before you type and every subsequent lookup is effectively free.
• Above 100,000 the tool switches to trial division up to the square root. At the input ceiling of 10,000,000 that is about 3,163 iterations, which is imperceptible.
• The primality test is not Miller-Rabin. It would be far too slow to reuse anywhere near 10 to the 18th, so do not lift this approach into a problem with large constraints.
• Divisors are found by walking i up to the square root of N and taking both i and N divided by i, which is why the list arrives complete after only about 3,163 steps at the ceiling.

Limits on N and What Gets Slow

• Input is clamped to 10,000,000. Typing more silently uses the ceiling rather than reporting an error, so check the number echoed in the factorisation line.
• 1 has no prime factors and the line says so, reading 1 (no prime factors). Zero and negatives produce no output at all.
• A prime input produces a single factor with no exponent and exactly 2 divisors. Try 99,991, which is prime and sits just below the sieve limit.
• The divisor panel scrolls rather than growing without bound. 1,000,000 has 49 divisors and a totient of 400,000, and the list is scrollable at that size.
• A highly composite number is the slow case for the divisor list, not the factorisation. The factorisation of 1,000,000 is 2 primes; enumerating its divisors is what takes the time.