[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
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 1018. 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.
The next non-zero entry is a
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 105 (all 9,592 of them) in a second or two. This will allow direct lookup of primes less than 105 and testing or getting factors numbers up to 1010 (since their largest prime factor will be less than 105 ).
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 = P1e1 x P2e2 x P3e3 .... x Pmem . For example 36 = 22 x 32. 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
Suggestions for Further Explorations
Copyright © 2000-2018, Gary Darby All rights reserved.