Prime factors #1

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.

 

Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

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 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.  

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 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.  

Find the smallest non-prime positive integer whose factors sum to 100.  

Find the smallest number of consecutive primes that sum to 106,620

Which 10 digit prime has the most 0's?, 1's?, 2's?, etc. up to 9's.

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

Done December 2005: TPrimes originally included a GetPrevPrime function.  I removed it since I hadn't had a chance to test it.  The most straightforward way is to successively subtract  2 starting from the largest odd number less than or equal to the input number and call IsPrime until it returns true.  

The displays of large numbers would be easier to read if they were formatted with commas.

Done December, 2005:  If you want to start working on the problems solved in PrimeFactors2, try these:

Find the smallest non-prime positive integer whose factors sum to 100.  

Find the smallest number of consecutive primes that sum to 106,620

Which 10 digit prime has the most 0's?, 1's?, 2's?, etc.

  
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2016, Gary Darby    All rights reserved.