# 3.2 Prime Factorization

Jump to:

- [Prime numbers]

**TODO**: Introduction

## Definition:

Prime, CompositeWe say an integer $n > 1$ is

primeif its only factors are 1 and $n$. If $n$ has factors other than 1 and itself, then we say it iscomposite. The number 1 is neither prime nor composite.

This should be nothing new. However, what may be new is the process of checking to see if a number is prime. Of course, to see if some $n$ is prime, we could test to see if any of $2, 3, … n-2, n-1$ divide it. However, we don’t need to check any even number greater than 2, since if any other even number divides $n$, then so will 2. We can still throw away many potential factors, though – see if you can notice a pattern below:

$$