Trial Division

As an integer n is composite iff it has a prime factor 1 < p < n, then a factor d of n can be found by testing if n divided by d is an integer for some 1 < d < n. If so, then d is a factor, and testing continues for n/d.

However, this is usually VERY slow, and only useful for small n, say n < 10⁹.

If no d satisfies the test, then n is prime.