Editing Trial division (section)

== Method ==
Given an integer ''n'' (''n'' refers to "the integer to be factored"), the trial division consists of systematically testing whether ''n'' is divisible by any smaller 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, the effort can be reduced by selecting only [[Prime_number|prime numbers]] as candidate factors. Furthermore, the trial factors need go no further than <math>\scriptstyle\sqrt{n}</math> because, if ''n'' is divisible by some number ''p'', then ''n = p × q'' and if ''q'' were smaller than ''p'', ''n'' would have been detected earlier as being divisible by ''q'' or by a prime factor of ''q''.

A definite bound on the prime factors is possible. Suppose {{mvar|P<sub>i</sub>}} is the {{mvar|i}}'th prime, so that ''P''<sub>1</sub> = 2, ''P''<sub>2</sub> = 3, ''P''<sub>3</sub> = 5, etc. Then the last prime number worth testing as a possible factor of ''n'' is {{mvar|P<sub>i</sub>}} where {{math|''P''<sup>2</sup><sub>''i''&nbsp;+&nbsp;1</sub> > ''n''}}; equality here would mean that {{math|''P''<sub>''i''&nbsp;+&nbsp;1</sub>}} 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 an integer, then it is a factor and ''n'' is a [[square number|perfect square]].

The trial division algorithm in [[Pseudocode|pseudocode]]:

 '''algorithm''' trial-division '''is'''
     '''input:''' Integer ''n'' to be factored
     '''output:''' List ''F'' of prime factors of ''n''
 
     ''P'' ← set of all primes &le; <math>{{\sqrt{n}}}</math>
     ''F'' ← empty list of factors
 
     '''for each''' prime ''p'' '''in''' ''P'' '''do'''
         '''while''' ''n'' '''mod''' ''p'' is 0
             Add factor ''p'' to list ''F''
             ''n'' ← ''n''/''p''
 
     '''if''' ''F'' is empty    ''(Original n is prime?)''
         Add factor ''n'' to list ''F''

Determining the primes less than or equal to <math>{{\sqrt{n}}}</math> is not a trivial task as ''n'' gets larger, so the simplest computer programs to factor a number just try successive integers, prime and [[Composite number|composite]], from 2 to <math>{{\sqrt{n}}}</math> as possible factors.