Factoring integers

The fundamental theorem of arithmetic says that every integer can be written as a product of prime numbers. We are going to look at algorithms for finding all the prime factors of a given integer.

For example, $6 = 2 \times 3$ where $2$ and $3$ are prime, and $91 = 7 \times 13$ where both $7$ and $13$ are prime.

Similarly, $193139816415 = 3 \times 5 \times 7 \times 13 \times 383 \times 571 \times 647$.

Algorithm 3.A: Factoring an integer given a list of known prime numbers

Describe an algorithm that finds all prime factors of a given integer $n$ where $n \ge 2$.

Input: an integer $n \ge 2$ and a table "PRIMES" of all prime numbers less than or equal to $\sqrt{n}$ starting in a entry labelled 0.
Output: a table "FACTORS" of all prime factors of $n$; you may assume this table is large enough to hold all prime factors.

For example, if $n = 1600$, your table would be:

PRIMES

012345 67891011
23571113 171923293137

Operations your computer can perform:

  • Create labelled values that can hold one integer each.
  • Create labelled tables where each entry has an integer label and can hold one integer.
  • Write and read integers to and from specific entries.
  • Add, multiply, divide and compare two integers.
  • Given two integers $m$ and $n$, find the remainder when one calculates $m \div n$.

Does your algorithm work on $12$? How about $969969$? How about the following, slightly different problem:

Algorithm 3.B: Factoring an integer

Describe an algorithm that finds all prime factors of a given integer $n$ where $n \ge 2$.

Input: an integer $n \ge 2$.
Output: a table "FACTORS" of all prime factors of $n$; you may assume this table is large enough to hold all prime factors.

Operations your computer can perform:

  • Create labelled values that can hold one integer each.
  • Create labelled tables where each entry has an integer label and can hold one integer.
  • Write and read integers to and from specific entries.
  • Add, multiply, divide and compare two integers.
  • Given two integers $m$ and $n$, find the remainder when one calculates $m \div n$.

For this problem, you do not know a priori any prime numbers.

Tabulating the results

Now, suppose you wanted to tabulate the results, but you can only create a table of a specific size. To create a sufficiently large table, you must know what is the maximum number of prime factors a number $n$ could have.

Of course, if the number is prime, the answer is $1$, but you may not know this, so the question is, what is the most factors that a number could have?

Come up with a formula that gives an upper bound on the number of prime factors. If you want to check you answer, click here.

Problems

1. Given that all prime numbers less than $\sqrt{10998}$ are

$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103$

find and tabulate all prime factors of $10998$ applying Algorithm 3.A. Recall that $2^{10} = 1024$.

2. How much more work would be required by your Algorithm 3.B?

Solutions

Here are our solutions to Algorithms 3.A and 3.B.