trial division
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 ≤ a2. 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 pre-screening: 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:
- Bressoud89 (has pseudocode (pp. 21-22))
- D. M. Bressoud, Factorizations and primality testing, Springer-Verlag, 1989. New York, NY, ISBN 0387970401. MR 91e:11150 [QA161.F3B73]
- Riesel94 (has a PASCAL version (pp. 7-8))
- H. Riesel, Prime numbers and computer methods for factorization, Progress in Mathematics Vol, 126, Birkhäuser Boston, Boston, MA, 1994. ISBN 0-8176-3743-5. MR 95h:11142 [An excellent reference for those who want to start to program some of these algorithms. Code is provided in Pascal. Previous edition was vol. 57, 1985.]