Trial division

This article page is a stub, please help by expanding it.

This article needs more work.

Please help by expanding it!

Trial division is the most basic deterministic primality test. The test determines successively whether an integer $\scriptstyle n\,$ is coprime to all primes up to $\scriptstyle \left\lfloor {\sqrt {n}}\right\rfloor \,$.

For example, to determine whether 24957 is prime or not, we could start by observing that its square root is roughly 157.977..., and thus we don't need to try dividing it by any primes greater than 157. The number is odd, so there's no need to try dividing it by 2. Dividing by 3 reveals that 24957 = 3 × 8319, so 8319 is not prime. We can divide 8319 by 3 again, yielding 2773. But is 2773 prime? Its square root is roughly 52.659..., so now we don't need to divide by any of the primes between 53 and 157, nor do we need to try dividing it by either 2 or 3. We can go ahead and try dividing by 5, by 7, by 11, etc. As it happens, 2773 = 47 × 59; the least prime factor of a nonsquare semiprime is the largest prime less than the square root.

A059396 Number of primes less than square root of n-th prime; i.e. number of trial divisions by smaller primes to show that n-th prime is indeed prime.

{0, 0, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, ...}

A189172 Largest prime number tried when factoring n using trial division.

{1, 1, 1, 2, 2, 2, 2, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 3, 3, 2, 3, 3, 3, 2, 5, 3, 3, 2, 5, 3, 5, 2, 3, 3, 5, 3, 5, 3, 3, 2, 5, 3, 5, 3, 3, 3, 5, 2, 7, 5, 3, 3, 7, 3, 5, 2, 3, 5, 7, 3, 7, 5, 3, 2, 5, 3, 7, 3, 3, 5, 7, 3, 7, 5, 5, 3, 7, 3, 7, 2, 3, 5, ...}

Worst case

This shows one of the major drawbacks of trial division, namely, when the number to be tested is an odd nonsquare semiprime and its least prime factor is close to its square root.

A046388 Odd numbers of the form p*q where p and q are distinct primes.

{15, 21, 33, 35, 39, 51, 55, 57, 65, 69, 77, 85, 87, 91, 93, 95, 111, 115, 119, 123, 129, 133, 141, 143, 145, 155, 159, 161, 177, 183, 185, 187, 201, 203, 205, 209, 213, 215, 217, 219, 221, 235, 237, 247, 249, ...}

A198512 Half the difference between an odd squarefree semiprime's factors.

{1, 2, 4, 1, 5, 7, 3, 8, 4, 10, 2, 6, 13, 3, 14, 7, 17, 9, 5, 19, 20, 6, 22, 1, 12, 13, 25, 8, 28, 29, 16, 3, 32, 11, 18, 4, 34, 19, 12, 35, 2, 21, 38, 3, 40, 6, 15, 24, 43, 17, 47, 27, 5, 18, 28, 9, 1, 20, 31, 10, ...}

For most numbers, it makes sense to start with the small primes and work up to the square root. For example, given 30 consecutive integers, 22 of those will have at least one of 2, 3 and 5 for a prime factor, but 8 of them will have a least prime factor greater than 5.

GCD method

One may consider the GCD of $\scriptstyle n\,$ with a product of consecutive primes, i.e. quotient of primorial numbers, to somewhat speed up the process. For example

$\gcd(n,31\#)=\gcd(n,2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23\cdot 29\cdot 31)=\gcd(n,200560490130)$

evaluates to 1 if and only if $\scriptstyle n\,$ is prime, for 1 < $\scriptstyle n\,$ < 1369 = 37^2. Then one may follow with

$\gcd(n,67\#/31\#)=\gcd(n,37\cdot 41\cdot 43\cdot 47\cdot 53\cdot 59\cdot 61\cdot 67)$

and so on.

A002110 Primorial numbers (first definition): product of first n primes. Sometimes written prime(n)#.

{1, 2, 6, 30, 210, 2310, 30030, 510510, 9699690, 223092870, 6469693230, 200560490130, 7420738134810, 304250263527210, 13082761331670030, 614889782588491410, 32589158477190044730, ...}

Specialized Rules

There are specialized rules which can be applied prior to trial division. A well known one is (base 10) numbers whose digit sum = 0 (mod 3) are themselves = 0 (mod 3). Another is (base 10) numbers with terminal digit 5 or 0 are = 0 (mod 5).