Factoring semiprimes using only addition

Methodology:

  1. 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
  2. For each dictionary entry — add the key to the value
  3. If the value == semiprime — then factor found
  4. If the value > semiprime — then remove this dictionary entry and all dictionary entries with a higher key
  5. 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 🙂