Fundamental Theorem of Arithmetic

Every natural number is either prime or composite with the exception of one number. Each composite number is built out of prime factors. We can decompose any composite number and represent it as a product of primes in the same way we think of chemical formulas representing atoms (for example, H₂O is water and is made up of two atoms of hydrogen and one atom of oxygen). The Fundamental Theorem of Arithmetic states this relationship:

QUESTION: How are the factors and prime factors of a number related?

Let N be a natural number with the prime factorization of N = p^aq^br^c... Then the number of factors (divisors) of N is found by the function
d(N) = (a+1)(b+1)(c+1) ...

EXAMPLE: N = 15 = 3¹*5¹ so d(N) = (1+1)(1+1) = 4
We know the four divisors of 15 are 1, 3, 5, and 15.

QUESTION: When checking if a number is prime, how many factors do we have to check?

We only have to check the prime numbers up to the square root of n. Any larger number that is a factor of n would have a "partner" factor less than it that we would have already checked for.

EXAMPLE: N = 1581
The square root of 1581 is approximately 39.76
Check all the primes up to 40
1581 = 31*51