
Glossary: Prime Pages: Top 5000: 
To see if an individual small integer is prime, trial division works well: just divide by all the primes less
than (or equal to) its square root. For example, to show 211 is prime, just divide by 2, 3, 5, 7, 11, and 13. Since none of these divides the number evenly, it is a prime. One curios way to reword this is as follows:
Theorem: Let a and n be integers such that a < n < a^{2}. n is prime if and only if gcd(n,a!) = 1. When looking for a large prime (say a titanic prime), we could never divide by all the primes less than the square root. However, we still use trial division for prescreening: that is, when we want to know if n is prime, we first divide by a few million small primes, then apply a primality test. The Sieve of Eratosthenes is usually faster for finding all of the primes in a list of consecutive integers. Wheel factorization is a variant of trial division which does not require us to keep a list of primes (but is slower).
See Also: WheelFactorization, SieveOfEratosthenes References:
Chris K. Caldwell © 19992015 (all rights reserved)
