Prime number
Definition: A prime number is a number that can be divided only by 1 and itself. This means that the number has exactly two factors.
For example, 13 is a prime number because 13 can only be divided evenly by 1 and 13.
If the number has more than two factors, we say that the number is composite.
For instance, 12 is a composite number because 12 can be divided by numbers other than 1 and 12, such as 2, 3, and 4.
1 is neither prime nor composite because it has only one factor. According to the definition, a number must have at least 2 factors before it can be prime or composite.
Notice also that 2 is the only number that is even and prime at the same time.
How many numbers less than 100 are prime?
You can use the definition to test every single number. It is somewhat timeconsuming.
As a shortcut, you can use a method or algorithm called Sieve of Eratosthenes, named after a famous Greek mathematician.
Sieve's Algorithm:
Make a list of all numbers from 1 to 100
Start by crossing out 1 because it is not prime. Then, circle the next number after 1 that is prime, which is 2
Cross out all the multiples of 2 until you get to 100, such as 2, 6, 8, 10, 12...
Look for the next number after 2 that is prime. That number is 3. Circle 3 and cross out all multiples of 3, such as 6, 9, 12, ...
Repeat the process with 5 and 7. After you are done, you should find 25 prime numbers.
We show you the process for all numbers from 1 to 50
Sieve of Erastothenes


The numbers that are circled and not crossed out are the prime numbers. There are 15 prime numbers between 1 and 50
Important observation:
The number 30 is crossed out by a blue, a red, and a green line. This means that 30 can be divided by 2, 3 and 5.
Prime factor test
The prime factor test will help you quickly determine if a number is prime or not. This will be very useful when the number is big.
To test for prime factor of a number x, just search for prime factors n of x, such as n
^{2} ≤ x
Example:
Is 301 prime?
Just search for prime factors n of 301 such as n
^{2} ≤ 301
17 × 17 = 289
19 × 19 = 361
Therefore, the prime factors you can use to do your test are 2, 3, 5, 7, 11, 13, and 17
2, 3, 5, 11, 13, and 17 cannot divide 301
However, 7 can divide 301 since 301 ÷ 7 = 43
Therefore, 301 is not a prime number.
As you see, the prime factor test made it easier to check if a 301 was prime. You only had to try dividing 301 by 7 numbers as opposed to trying all numbers from 1 to 301
Prime Factorization
Every composite number can be written as the product of prime numbers. When a number is written as the product of primes number, we call the expressed product prime factorization.
For instance, do the prime factorization of 40 and 24.
let us start with 40
Start by dividing 40 by 2, you get 40 = 2 × 20
Divide 20 by 2 again because 20 can be divided by 2. You get 20 = 2 × 10
So far, we have 40 = 2 × 2 × 10
Divide 10 by 2 to get 10 = 2 × 5.
5 is prime, so you are done!
Thus, 40 = 2 × 2 × 2 × 5
Find prime factorization for 63.
63 cannot be divided by 2, so try the next number after 2, which is 3.
63 divided by 3 is 21, so 63 = 3 × 21
21 can be divided by 3 once again to get 7, so 21 = 3 × 7.
7 is prime, so you are done!
Thus, 63 = 3 × 3 × 7.
Prime number quiz
Take the quiz below to see how well you understand this lesson.

Apr 02, 20 12:05 PM
Find out how to become an operations research analyst if you have a math major.
Read More
New math lessons
Your email is safe with us. We will only use it to inform you about new math lessons.