### Problem Description

This program, **PrimeFactors1**, leads us into the interesting world of primes and factors. It
contains a unit with functions **GetNextPrime** ( get the first prime
higher than a given number), **IsPrime** (returns true or false
depending on whether a given number is prime), and **GetFactors** (returns an
array of the prime factors of a given number). It
handles numbers up to 10^{18}. The follow-on program,
PrimeFactors2, will use the routines developed here to solve a number of related
problems.

### Background and Discussion

We'll use the **Sieve of Erastothenes** technique to generate an
initial set of primes. It works like this: Initialize an array with consecutive
integers, starting with 2. Now search for the first non-zero entry.
If we find one in the first half of the table, successively add that number to
the position and set the resulting entry to zero for the rest of the
table. So, for example, the first non-zero in the table below is
"2" in the 1st position. So we zero out positions 3,5,7,
etc.

2,3,~~0~~,5,~~0~~,7,~~0~~,9,~~00~~,11,~~00~~,13,~~00~~,15....(number)

**1,2,3,4,5,6,7,8,09,10,11,12,13,14...**.(position)

The next non-zero entry is a~~ ~~"3' in
position 2, so we successively add 3 to position 2 and set positions 5,8,11,14,
etc to zero.

2,3,~~0~~,5,~~0~~,7,~~0~~,~~0~~,~~00~~,11,~~00~~,13,~~00~~,~~00~~...(number)

**1,2,3,4,5,6,7,8,09,10,11,12,13,14...**(position)

By the time we get halfway through the table, only primes are
left which we can then pack by removing all the 0's from the
table.

Now that we have done that, we can finish filling the table
by generating primes by a brute force trial and error method.
Take the highest prime in the table, add 2 (it's an odd number and we know there
won't be anymore even primes), then for table entries less than or equal to the
square root of this number, try dividing by the number and check for a
remainder. The modulo function does this nicely since, by definition, ** n
mod m** is the remainder when ** n** is divided by ** m.**

All of this initialization is done in as the program starts in
the **Create **constructor method of a **TPrimes** object. If you
override a constructor, always call the constructor of the ancestor object
first, **TObject** in this case. An instance of **TPrimes**,
named **Primes**, is created in the **Initialization** section of the
unit. Prime numbers are created up to 10^{5} (all 9,592 of
them) in a second or two. This will allow direct lookup of primes less
than 10^{5} and testing or getting factors numbers up to 10^{10 }(since
their largest prime factor will be less than 10^{5} ).

The functions themselves are straightforward as is the main
unit, **U_Primefactors1**, which calls the functions to display
primeness (primality?) or factors for input numbers. I've copied the
source code for the **U_Primes** unit here for browsing since it's the most
interesting part. Downloaded source has both units.

**Addendum December 31, 2005: ** Here is the first
update since the program was originally posted in 2002. A viewer found a
minor typo and while correcting that, I saw that I had promised a
"Prime factors 2" to solve a few prime number or factoring
problems.

Rather than create a new program, I have included
solutions to the first two problems as part of Prime Factors
1. The third problem is the most challenging and interesting enough
that it will likely be used as a problem for Project Euler. For that
reason, I haven't posted the solution here, but will do so later this
year.

The **TPrimes** class introduced has been enhanced to include
the **GetPrevPrime** function and moved
into a **MathsLib** unit which is included here with the source
code zip file and is also now included in our common library file
DFFLIBV04.

**Addendum January 9, 2006: ** Three additional methods were
added to the **TPrimes** class in the **MathsLib** unit and are
tested in today's version of Prime Factors1. *GetCanonicalFactors(N)*
method returns a new *CanonicalFactors* array of integer pairs the first of
which represents a unique prime factor and the second indicating the number of
occurrences of that factor. If **N** has **m** unique
prime factor values then the canonical form of the factorization is **N
= P1**^{e1} x P2^{e2} x P3^{e3} .... x Pm^{em} .^{ }
For example 36 = 2^{2} x 3^{2}.
The second new method is *GetNbrDivisors(N)* ** **which returns the total
number of divisors of **N**. Since each of the **Px**,
factors can occur 0 to **ex** times, there are **(ex+1)** ways that
multiples of **Px** can occur in each divisor and **(e1+1) x (e2 +1) x (e3 +
1) .... x (em +1) **total divisors of** N**. The third
new method is *GetDivisors(N)* which returns a new *Divisors* array
with the divisors of **N**.

**Addendum January 28, 2006**: Charles Doumars, who's
hobby is making my code better, has enhanced the TPrimes unit to handle
primes up to 18 digits in length and do it rather efficiently both for factoring
into prime factors or testing numbers for "primeness". I've
modified Primefactors1 to let you enter and factor the new larger
numbers.

### Running/Exploring the Program