Extract prime factors and exponents
Shrink the remaining number while preserving the original when needed.
Understand the idea
Try p from 2 while p ≤ remaining/p. Repeatedly divide out p and count its exponent. After all smaller possibilities are excluded, a leftover greater than 1 is prime and contributes exponent 1.
Trace a small example
For 72, division by 2 produces 36, 18, 9, giving exponent 3. Division by 3 produces 3, 1, giving exponent 2. Thus 72 = 2³ × 3²: two distinct prime factors, but five factors with multiplicity.
#include <iostream>
int main() {
long long remaining = 180;
for (long long p = 2; p <= remaining / p; ++p) {
int exponent = 0;
while (remaining % p == 0) {
remaining /= p;
++exponent;
}
if (exponent) std::cout << p << ' ' << exponent << '\n';
}
if (remaining > 1) std::cout << remaining << " 1\n";
}Conditions and cost
A safe worst-case bound is O(√n) for the original n. For n = 1 the factorization is empty. A shortened prime list must cover every candidate required by the leftover proof.
After trial division stops with remaining > 1, what is left?
Turn the idea into code
Factor 180 and give its distinct-factor and multiplicity counts.
Give me a hint
Divide out all copies of each factor.
Show the explained solution
180 = 2² × 3² × 5. There are 3 distinct prime factors and 5 with multiplicity.
Your notes
Mark complete when you can explain it yourself.