Trial Division - Method

Method

Given an integer n (throughout this article, n refers to "the integer to be factored"), trial division consists of testing whether n is divisible by any number. Clearly, it is only worthwhile to test candidate factors less than n, and in order from two upwards because an arbitrary n is more likely to be divisible by two than by three, and so on. With this ordering, there is no point in testing for divisibility by four if the number has already been determined not divisible by two, and so on for three and any multiple of three, etc. Therefore, effort can be reduced by selecting only prime numbers as candidate factors. Furthermore, the trial factors need go no further than because, if n is divisible by some number p, then n = p×q and if q were smaller than p, n would have earlier been detected as being divisible by q or a prime factor of q.

A definite bound on the prime factors is possible. Suppose P(i) is the ith prime, so that P(1) = 2, P(2) = 3, P(3) = 5, etc. Then the last prime number worth testing as a possible factor of n is P(i) where P(i + 1)2 > n; equality here would mean that P(i + 1) is a factor. Thus, testing with 2, 3, and 5 suffices up to n = 48 not just 25 because the square of the next prime is 49, and below n = 25 just 2 and 3 are sufficient. Should the square root of n be integral, then it is a factor and n is a perfect square.

An example of the trial division algorithm, using a prime sieve for prime number generation, is as follows (in Python):

def trial_division(n): """Return a list of the prime factors for a natural number.""" if n == 1: return primes = prime_sieve(int(n**0.5) + 1) prime_factors = for p in primes: if p*p > n: break while n % p == 0: prime_factors.append(p) n //= p if n > 1: prime_factors.append(n) return prime_factors

Trial division is guaranteed to find a factor of n if there is one, since it checks all possible prime factors of n. Thus, if the algorithm finds one factor, n, it is proof that n is a prime. If more than one factor is found, then n is a composite integer. Another way of saying this, which is more advantageous computationally, is that if any prime whose square does not exceed n divides it without a remainder, then n is not prime.