Algorithm 3.A

Colloquial solution

Our colloquial algorithm is:

Given $n$:

  1. Starting with the smallest prime $p$ in the table:
    1. If the number $n$ is divisible by $p$, record that $p$ as a divisor and divide $n$ by $p$, after which if $n = 1$, we have found all the prime divisors of $n$; otherwise, repeat Step 1a.
    2. Go to the next prime number $p$ in the table, and return to Step 1a.

Detailed algorithmic solution

The table PRIMES has entries PRIMES0 = 2, PRIMES1 = 3, PRIMES2 = 5, PRIMES3 = 7, etc.

Our algorithm is:

1. Create a cell labelled "k" and give that cell the value $0$.

2. Create a cell labelled "n" and give that cell the value $n$.

3. Create a cell labelled "m" and give that cell the value $0$.

4. If "n" divided by the value of PRIMES"k" has a remainder of zero,

  1. Divide the value in "n" by PRIMES"k".
  2. If "n" = $1$, we are finished.
  3. Copy the value PRIMES"k" to FACTORS"m".
  4. Add 1 to "m".
  5. Return to Step 4.

Otherwise, "n" is not divisible by PRIMES"k" and thus add 1 to "k".

5. If PRIMES"k" still refers to a prime number in the table PRIMES, return to Step 4.

Otherwise, we are finished.

Output

There are "m" factors stored in entries FACTORS0, ..., FACTORS"m" - 1.