- Create a dictionary. Add keys for all primes below the square root of the semiprime (or just odd numbers, if you don’t have a list of the primes), and set the value to be the same as the key
- For each dictionary entry — add the key to the value
- If the value == semiprime — then factor found
- If the value > semiprime — then remove this dictionary entry and all dictionary entries with a higher key
- Repeat until factor found
Why does this work?
Simply put, the semiprime is the product of two primes. For example — 3 * 7 = 21. As such — 7 lots of 3’s (3+3+3+3+3+3+3) and 3 lots of 7’s (7+7+7) = 21. All day, every day.
Is it a fast way to factor semiprimes?
Nope. Not even close. It’s just a mathematical constraint-based curiosity — and I like those 🙂