Education Technology

Solution 11865: The is Prime() Algorithm on the TI-89 Family, TI-92 Family, and Voyage™ 200 Graphing Calculators.

What is the is Prime() algorithm?

The algorithms used by the TI-89 family, TI-92 family, and Voyage 200 calculators divides by successive primes through the largest one less than 216. It does not actually keep a table or use a sieve to create these divisors, but cyclically adds the sequence of increments 2, 2, 4, 2, 4, 2, 4, 6, 2, 6 to generate these primes plus a few extra harmless composites.

TI-92 Plus and TI-89 family start the same way, except that they stop this trial division after trial divisor 1021, then switch to a relatively fast Monte-Carlo test that determines whether the number is certainly composite or is almost certainly prime. The is Prime() function stops at this point returning either false or (almost certainly) true.

If the number is identified as composite, the factor() function then proceeds to the Pollard Rho factorization algorithm. It is arguably the fastest algorithm for when the second largest prime factor has less than about 10 digits. There are faster algorithms for when this factor has more digits, but all known algorithms take expected time that grows exponentially with the number of digits. For example, the Pollard Rho algorithm would probably take centuries on any current computer to factor the product of two 50-digit primes. In contrast, the is Prime() function would quickly identify the number as composite.

Both the compositivity test and the Pollard Rho algorithm need to square numbers as large as their inputs, so they quit with a Warning: ... Simplification might be incomplete, message if their inputs exceed about 307 digits.

Additional information on this algorithm can be found in D. Knuth, The Art of Computer Programming, Vol 2, Addison-Wesley.