Introduction

The Fundamental Theorem of Arithmetic states that any positive integer can be written as the product of a unique set of prime numbers, called its prime factors. Some examples:

• 20 = 2 x 2 x 5
• 33 = 3 x 11
• 285 = 3 x 5 x 19
• 37 = 1 x 37

Obviously 1 is a factor of any integer and does not need to be included in the set, though if the number is prime, as for 37 above, including 1 makes the action of taking a product clearer. Finding the factors of small numbers is quite easy but factorising large numbers is tedious if done manually, hence the use of a program to do the work.

Factors on the hp 39g+ Graphing Calculator

Factors uses the simple technique of repeated trial divisions to find the prime factors of a number, i.e. it starts by dividing by 2, then 3, 5, 7, 9, 11, 13, 15 etc. If there is no remainder in the division that number is a factor and is added to the list. This method is not very efficient for factorising large numbers but the faster methods which exist (Dixon's algorithm, quadratic sieve) are more complex and would result in a much larger program and also require a considerable amount of memory to store intermediate results.

Factors will find the prime factors of numbers of up to 12 digits, returning the result as a list in L0. 12 digits is the largest number the hp 39g+ can store exactly as an integer. The program returns 1 as the first element in the list, partly so that 1 itself can be factorised, and partly to simplify programming because the calculator apparently cannot handle empty lists. The other factors are appended in numerical order, with factors appearing more than once if necessary, e.g. the factors of 5684 are returned as {1,2,2,7,7,29} so that multiplying them all together yields 5684.

The time taken to find the prime factors obviously depends on the size of the number and how many (small) factors it has. It can vary from seconds up to potentially several hours for a large number which is prime.

Loading Factors

Copy the files HP39DIR.000, HP39DIR.CUR and FACTORS0.00 to an empty directory on a PC, start the HP39G Connectivity program and point it to the directory holding the files, and transfer Factors from the computer into the PROGRAM catalog part of the hp 39g+'s memory using the RECV option on the calculator.

Running Factors

Run program Factors from the calculator's program catalog. A screen such as Figure 1 is shown where you enter the number you wish to factorise.

Figure 1 - Number entry

The default number shown is the current contents of variable N so this could be assigned the correct value before running Factors. Another useful 'trick' is that if you enter a number on the bottom line of the home screen display, but do not press ENTER, then switch to the program catalog and run the program, the previously typed number will appear on the input line and you just need to press ENTER to complete entry.
As normal on an entry screen expressions such as 2^17+1 can be entered as well as just numbers.

After entering the number the display changes to Figure 2 while factors are being found.

Figure 2 - Factorising the number

A percentage completed indicator is shown to give an idea of how long factorisation is going to take. In practice this is a pessimistic estimate since it assumes no more factors will be found, and usually it speeds up as calculation proceeds.
(In fact displaying a constantly updated percentage slows down the program and it will run about 40% faster if you delete the statement DISP 3;INT(100*Y/U)"%":, though you will be left looking at an unchanging screen wondering if anything is happening.)

Once factorisation is complete the display changes to Figure 3 to show the results. The display is 'frozen' at this point to allow it to be read; press any key to return to the program catalogue. Unfortunately the DISP statement on the hp 39g+ does not wrap text onto the next line so if there are more than a few factors they will disappear off the end of the line. Changing to the HOME screen and recalling list L0, or changing to the LIST EDITOR and editing L0, will allow all the values to be seen.

Figure 3 - Factors found

If the entered number is prime then the list will just contain 1 and the number.

Hardware Requirements

Factors runs on a Hewlett-Packard 39g+ calculator. It should also work on the 38g, 39g and 40g but will take about three times as long to find factors, due to the slower processor. It is written in HP-BASIC and may work on the 48g, 49g and 50g but has not been tried.

The program takes up 1.4 kilobytes of RAM when run. It also uses typically a few tens of bytes to store list L0.

Variables Used

Factors uses the HOME variables L, N, U, X & Y, and list L0, and will therefore overwrite any existing information stored in them, though the number to be factorised is retained in N.

Limits

The number to be factorised must be between 1 and 1x10¹². Entering zero repeats the prompt (since 0 has no prime factors), negative numbers are treated as positive and real numbers are truncated to integers.
Thus -365.789 is treated as 365.

Known Bugs

Other than the slowness of the algorithm for large prime numbers, none are known.

Program Listing

Note: the character Þ represents the 'STO' arrow.
True line breaks in the program are shown by ¿, other line breaks are just to fit the listing into the table.