Skip to the content

Math 2.0

Number theory Concept

Trial division

Summary

Trial division is the simplest method to factor an integer $n > 1$ or to test whether it is prime. It divides $n$ by the integers $d = 2, 3, 4, \dots$ in turn, and it stops at the first $d$ that divides $n$ , or when $d^2 > n$ . If no $d$ with $d^2 \le n$ divides $n$ , then $n$ is prime.

Remarks

The method is correct because a composite number has a prime factor at most its square root. It is enough to test the primes $d$ , but a test of all integers $d$ is also correct. For a number $n$ with $k$ digits, the method can need about $\sqrt{n} \approx 10^{k/2}$ divisions. Thus it is slow for large $n$ .

Further reading

Web https://en.wikipedia.org/wiki/Trial_division, Method

About this page

Tag	`0Z962ECCXR`
URI	`m2://0Z962ECCXR`
Kind	concept
Writing	W1 stated
MSC	11Y05
Specializes	Primality test
Same as	Wikidata Q1333681 Wikipedia Trial division

Markdown · JSON · Edit on GitHub

What this page needs for W2

edge defines in: at least one definition (0 of 1)
edge instance_of in: at least two examples (0 of 2)
edge not_instance_of in: at least one non-example (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.