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.