# Prime Number

A natural number $p>1$ is called *prime* (or a prime number) if its only positive divisors are 1 and $p$ itself. Otherwise, $p$ is called *composite*.

Converting this page mostly for Competitive Programming.

Problems:

- Generate Prime Numbers → use Sieve of Erastosthenes
- Primality Test
- Prime Factorization
- A lot of ways to do this, I’m not sure which one to choose
- Apparently you can use Floyd’s Cycle-Finding Algorithm to solve!! That is insane

### Propositions and Theorems (From MATH135)

**Prime Factorization (PF)**
Every natural number $n>1$ can be written as a product of prime.

**Euclid’s Theorem (ET)**
The number of primes is infinite.

**Euclid’s Lemma (EL)**
For all integers $a$ and $b$, and prime numbers $p$, if $p∣ab$, then $p∣a$ or $p∣b$.

**Proposition 14**
Let $p$ be a prime number, $n$ be a natural number, and $a_{1},a_{2},…,a_{n}$ be integers. If $p∣(a_{1}a_{2}…a_{n})$ , then $p∣a_{i}$ for some $i=1,2,…,n$

**Unique Factorization Theorem (UFT)**
Every natural number $n>1$ can be written as a product of prime factors uniquely, apart from the order of factors.

**Finding a Prime Factor (FPF)**
Every natural number $n>1$ is either prime or has a prime factor less than or equal to $n $.

**Divisors From Prime Factorization (DFPF)**
Let $n$ and $c$ be positive integers, and let

$n=p_{1}p_{2}…p_{k}$
be a way to express $n$ as a product of the distinct primes $p_{1},p_{2},…,p_{k},$ where some or all of the exponents may be zero. The integer $c$

$c∣n⟺c=p_{1}p_{2}…p_{k},where0≤β_{i}≤α_{i}fori=1,2,…,k$

**GCD From Prime Factorization (GCD PF)**
Let $a$ and $b$ be positive integers, and let

$a=p_{1}p_{2}…p_{k}$, and $b=p_{1}p_{2}…p_{k}$
be ways to express $a$ and $b$ as products of the distinct primes $p_{1},p_{2},…,p_{k}$, where some or all of the exponents may be zero. We have
$g(a,b)=p_{1}p_{2}…p_{k}whereλ_{i}=min{α_{i},β_{i}}fori=1,2,…,k$