Category:Trial division

From LiteratePrograms
Jump to: navigation, search

Trial division, perhaps the simplest algorithm for factoring and primality testing, simply attempts to divide a number by all possible factors. Divisions that have no remainder (go in evenly) reveal factors. We only have to test up to the square root of n, since if x is a factor, so is n/x. If no factors between 2 and \sqrt{n} (inclusive) are found, the number is prime.

hijacker
hijacker
hijacker
hijacker

Pages in category "Trial division"

The following 2 pages are in this category, out of 2 total.