September 12, 1997

Basic routine simplifies factoring

Alan Land, Keystone Digital Co, Pittsburgh, PA

Logarithms greatly simplify mathematical operations. Factoring, however, presents a problem: Pocket calculators are clumsy when it comes to that operation. The program factor.bas (Listing 1) is a convenient alternative if you want to obtain results in 3 minutes or less (that is, turn on the computer, put the disk in the b: drive, select "qbasic," run the program, enter the number, obtain results, and go back to work).

The input range is integers-only, from 2 to 2,147,483,647. The largest prime number is 131,071, the 12,251st prime. The program produces complete or incomplete factorizations. Incomplete factorizations are always correct but have a factor greater than 131,071. A complete factorization always appears with all terms in parentheses; for example,

120=(2 3)*(3 1)*(5 1).

The incomplete factorizations appear as

65,289,755=567,737*(5 1)*(23 1).

Yet a third format is

567,737=(567,737)*.

The third format indicates that the number is prime. Within the range that the program cites, enter only the integer--not any symbols, such as commas or decimal points. The range, 2³¹­1, and the number of primes, 12,251, are based on QBasic's long-integer array mechanism. It just so happens that the 12,251st prime is also 2¹⁷­1. Make sure that you do not use a tracer on this program; you need to reset to get out of the loop. The program takes approximately 1 minute to load all the primes. With the tracer on, loading might take about a day. (Click here to download Listing 1.) (DI #2083)

| EDN Access | Feedback | Table of Contents |