How to: Prime vs Composite Numbers

You may have a vague memory and understanding that numbers come in two forms: prime numbers and composite numbers. (Or at least prime and not prime.) Both of these terms have to do with a number’s factors, or smaller whole numbers (factors) that can be multiplied together to produce the number being investigated (the product).

Remember the structure of a multiplication problem : factor $\times$ factor $=$ product

Check out my step-by-step blog post on how to factor numbers with several examples if factoring doesn’t seem at all familiar.

A prime number has only two factors: the number itself and 1. In other words, the only way to multiply two whole numbers together to get the prime number is $1 \times$ the number itself.

A composite* number has other factors. In other words, there is some other pair of whole numbers that can be multiplied together to create the number in question.

*I personally take issue with the word composite here as it takes on a completely different, and easily confused, meaning in algebra. Hey math community: can we work on this language for consistency throughout the curriculum?

This post was originally published on mathteacherbarbie.com. If you are viewing it anywhere else, you are viewing a stolen copy.

Step 0: Know your basic multiplication facts

Weaknesses in multiplication facts will cause stumbling here. My personal belief based on working with students ranging from upper elementary through college, this single practice of really, deeply, automatically knowing the multiplication tables saves a whole lot of confusion and frustration throughout almost all math topics from factoring onward. Knowing the facts automatically and fluently will make many math topics much more accessible. If you need more research-backed ideas how to increase multiplication fluency, check out my post How to Learn Multiplication Facts: A Roundup.

Step 1: Memorize the rules for 0, 1, 2, and 3

0 and 1

Zero and one are neither prime nor composite. They are in a weird, unnamed category all by themselves. This is because they have unusual multiplication properties. $0 \times$ anything is always $0$, no matter what it’s multiplied by. No other number can do this. $0$ is unique.

$1\times$ anything is always the other thing, and $1\times 1=1$. $1$ is called the multiplicative identity because any number keeps its identity when multiplied by $1$. (This becomes extremely useful later in math, starting with fractions and well into higher levels of math. We can take advantage of this fact that multiplying by one keeps a number the same to change what the number looks like but still keep it the same number underneath. Kind of like changing one’s hair color but still remaining the same person.)

2 and 3

Two and three are both prime. They are the smallest two prime numbers. As we’ll see, $2$ has the distinction of being the only even prime number. (This is because every even number besides $2$ will have $2$ as a factor.)

Sieve of Eratosthenes

A common way of keeping track of prime vs composite numbers is known as the Sieve of Eratosthenes. Using this allows us to “sift (or sieve) out” the composite numbers, leaving behind the prime numbers. It is named after an ancient Greek mathematician/philosopher/scientist (mostly the same thing in those days).

While I personally have not learned of any earlier uses of this strategy, I want to acknowledge that we teach a very Eurocentric version of mathematics here in the U.S. and that frequently these named strategies, especially those named after Ancient Greeks and Romans were discovered earlier by other civilizations.

The Sieve (as I will call it for short) as it is currently presented starts with a 100-table typically used in the elementary grades. Students are led through the table systematically, number-by-number, circling prime numbers and crossing out composite numbers. We’ll do that here as we go. We can already start by crossing out $1$ and circling (or highlighting in our case) $2$ and $3$.

1*	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

Step 2: Is it divisible by 2?

The divisibility rule of 2

There are three practical ways of asking this question, and you get to pick your favorite:

• Is it an even number?
• Can it be halved (or shared between 2 people) evenly?
• Does it end in 0, 2, 4, 6, or 8?

Let’s work with the numbers 143 and 420 to illustrate each of these steps.

143	420
143 is not even 143 can not be halved or shared evenly between two people 143 ends in 3, which is not 0, 2, 4, 6, nor 8 So 143 is not divisible by 2. So 143 might be prime. We need to investigate further.	420 is even 420 can be halved ($210+210$) 420 ends in 0, which is on our list So 420 is divisible by 2! So 420 is composite. We already have our answer (though we’ll keep using this example to illustrate each test).

What numbers have a factor of 2 and thus are composite?

All even numbers greater than $2$ will be composite because they will always have $2$ as a factor. $2$ is the only prime even number.

Tracking the primes: Our sieve after considering 2

We can now cross out all even numbers except $2$ on this table, since they all are composite with a factor of $2$.

1*	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

Step 3: Is it divisible by 3?

The divisibility rule of 3

Check first: If you know your 3s table really well, then ask yourself: is this number on the 3s table? If so, then 3 is a factor and the number is composite. If you don’t know the table well, or if it’s too big to be on the 3s table, then the following divisibility rule should help.

A number is divisible by 3 (in other words, 3 is a factor) if you add up the digits and the result is divisible by 3.

143	420
The digits are 1, 4, and 3. $1+4+3=8$ 8 is not on the 3s table 8 is not divisible by 3. So 143 is not divisible by 3. So 143 still might be prime. We need to investigate further.	The digits are 4, 2, and 0. $4+2+0=6$ $6=3\times 2$ So 6 is divisible by 3. So 420 is divisible by 3! So 420 is composite. (We already knew this from the 2s above, but we’ll keep using it as an illustration).

What numbers have a factor of 3 and thus are composite?

Every third number will be a multiple of 3: 6, 9, 12, 15, etc. Each of these will be composite because $3$ will be a factor.

Any number that meets the divisibility rule of 3 above is composite since it has a factor of $3$.

Tracking the primes: Our sieve after considering 3

1*	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

Step 4: Is it divisible by 4?

If we go through in order, we don’t have to test composites

We know that 4 is divisible by 2, and 2 is a factor of 4.

Turns out that 2 will also be a factor of anything 4 is a factor of.

Since we’ve already figured out that all multiples of 2 are composite, that means all multiples of 4 are also composite.

Since it’s much easier to test for 2s (evenness, halve-ability, and/or last digit check), testing for 4 doesn’t really add much to this question of primeness or compositeness.

This will be true for all composite numbers! This is part of why The Sieve is useful. It helps us stay methodical and keep our place, while letting us know which ones we don’t have to test (at least not for primeness and compositeness).

Step 5: Is it divisible by 5?

The prime-ness of 5

First, let’s note that none of the smaller numbers we’ve tested so far have divided 5. (In other words, 5 was not knocked out of our Sieve anywhere along the way so far.) So 5 must not have smaller whole number factors.

Thus, 5 is a prime number, and we’ll highlight it in our sieve and use it in our tests for other numbers.

The divisibility rule of 5

Does the number end in 0 or 5? If so, it’s divisible by 5 and 5 is a factor. If not, then 5 is not a factor.

143	420
The last digit is 3. 3 is not 0 nor 5. So 143 is not divisible by 5. So 143 still might be prime. We need to investigate further.	The last digit is 0. So 420 is divisible by 5! So 420 is composite. (We already knew this.) 420 is divisible by 2, 3, and 5!

What numbers have a factor of 5 and thus are composite?

Numbers whose last digit (the digit in the ones place) is 0 or 5 are divisible by 5.

Numbers ending in any other digit (1, 2, 3, 4, 6, 7, 8, or 9) are not divisible by 5.

Tracking the primes: Our sieve after considering 5

1*	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

Step 6: Is it divisible by 6?

Remember? We don’t have to test composites

We know that 6 is divisible by 2 and by 3.

Turns out that both 2 and 3 will also be a factor of anything 6 is a factor of.

Since it’s much easier to test for 2s and 3s, testing for 6 doesn’t really add much to this question of primeness or compositeness.

This will be the last composite number I talk about as a step, since they’re not actually useful steps.

Step 7: Is it divisible by 7?

The prime-ness of 7

First, let’s note that none of the smaller numbers we’ve tested so far have divided 7. (In other words, 7 was not knocked out of our Sieve anywhere along the way so far.) So 7 must not have smaller whole number factors.

Thus, 7 is a prime number, and we’ll highlight it in our sieve and use it in our tests for other numbers.

The divisibility rule of 7

This is not an easy rule to remember. You might find it easier to divide using your favorite method and find out whether the division comes out as a remainder rather than memorizing this rule. Up to you!

The 7s rule has us splitting the last digit off of our number and dealing with the last digit and all the other digits. Take the last digit, double it, and subtract it from the other digits as though they were a number in and of themselves. If the result is divisible by 7, so was your original number.

143	420
The last digit is 3. Double the 3: $3\times 2=6$. Subtract 6 from the other digits (14). $14-6=8$ 8 is not divisible by 7. So 143 is not divisible by 7. So 143 still might be prime. We need to investigate further.	The last digit is 0. Double the 0: $0\times 2=0$. Subtract 0 from the other digits (42). $42-0=42$ 42 is on the 7s table ($7/times 6=42$) So 42 is divisible by 7. So 420 is divisible by 7! So 420 is composite. (We already knew this.) 420 is divisible by 2, 3, 5, and 7!

What numbers have a factor of 7 and thus are composite?

All numbers that fit the divisibility rule above have a factor of 7 and are composite.

Every 7th number after 7 is divisible by 7 and is composite: 14, 21, 28, 35, 42, etc.

Tracking the primes: Our sieve after considering 7

1*	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

Step 8: Is it divisible by 11?

The prime-ness of 11

According to our Sieve, 11 is the next prime number. We’ll highlight it and use it in our tests for bigger numbers.

The divisibility rule of 11

To determine whether 11 is a factor,

Add together the digits in every other place value.

Then add the other digits together.

Find the difference between the two sums.

If the difference is 0 or a multiple of 11, then the original number is divisible by 11.

143	420
Every other digit: 143 Add them together: $1+3=4$ The other digits: 4. Subtract: $4-4=0$ $0$ is 0 or a multiple of 11 So 143 is divisible by 11. So 143 is composite! It is divisible by 11.	Every other digit: 420 Add them together: $4+0=4$ The other digits: 2 Subtract: $4-2=2$ $2$ is not a multiple of 11 So 420 is not divisible by 11! But we already know 420 is composite. 420 is divisible by 2, 3, 5, and 7.

What numbers have a factor of 11 and thus are composite?

All numbers that fit the divisibility rule above have a factor of 11 and are composite.

Every 11th number after 11 is divisible by 11 and is composite: 22, 33, 44, 55, 66, 77, 88, 99, 110, 121, etc.

Tracking the primes: Our sieve after considering 11

1*	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

Step 9: Notice that we’ve found all the composites and primes between 1 and 100

I don’t know if you spotted it, but that last test, the 11s, didn’t actually lead us to cross off any new composite numbers that hadn’t been crossed off before. (To get to the first newly discovered (by us) composite number, the chart would have had to go up to at least 121.)

Turns out, this is a sign that we have identified all of the numbers between 1 and 100 as either composite or prime (except, of course, 1 which is neither).

We can highlight our Sieve accordingly.

1*	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

Here’s an interesting fact: the primes have no predictable pattern! It is actually quite cutting-edge research to continually find the “next prime number.” They don’t follow a pattern so each new potential prime has to be tested just as we are doing here! Some of these numbers are HUGE and require massive amounts of computing power to test over and over again with bigger and bigger prime numbers.

Step 10: Continue testing for prime factors by dividing

From here on out, there may be divisibility tests, but the ones that have been discovered are pretty complicated and usually not worth memorizing (unless you’re just into that sort of thing! Could be a good party trick.)

So instead, we’re going to test each next prime by actually dividing to determine whether it divides evenly.

If the question is just “is it prime or composite?” then, of course you can stop as soon as you find any prime factor. But let’s pretend we hadn’t found any factors of either of our examples, and test for 13.

143	420
We can try long division. Or we might be able to count by 13s… 13…26…39…52…65…78…91…104…117…130…143 143 is a multiple of 13! So 143 is divisible by 13. Turns out $143=11\times 13$, so its factors are 11 and 13.	Probably long division will be best. When we do that division, $420\div 13=32 R4$ The division has a remainder. So 420 is not divisible by 13! But we already know 420 is composite. 420 is divisible by 2, 3, 5, and 7.

For each successive prime (17, 19, 23, etc), you would divide similarly.

Step 11: Know when you’re done

If the question you’re answering is “Is ___ prime or composite?” you’re done and can answer composite as soon as you find any number that divides it. (I know, I know, I kept going with 420 when I could have stopped after Step 2. But it was a conscious choice.)

If, however, none of the numbers seem able to divide it, when can you answer prime?

Use the division results. Remember that the parts of a division problem are

dividend $\div$ divisor $=$ quotient $R$ remainder

If the divisor is bigger than the quotient, you’re not done yet. But as soon as the quotient starts being the bigger number of the two, then you’re done and you can confidently state that the number is prime.

Step 12: State your answer clearly, visibly, and directly

Always an important skill to develop, both inside and outside of math, is stating your results. The sense of relief after an 11-step process is great and we often just want it to be over with. But it’s important to communicate the results. Without communicating what we found, we’re the only ones who know (and we’re likely to forget too!) In our examples, we found that…

143 is composite. Its prime factors are 11 and 13.

420 is composite. Its prime factors are 2, 3, 5, and 7.

All of the numbers highlighted in our Sieve are prime.

All of the numbers, except 1, scratched out in our Sieve are composite.

*Whew* What a long and tedious process. But I promise that it gets faster and easier to spot and do with practice. And with confident and fluent knowledge of the multiplication tables!

You’ve Got This!