Prime Numbers with Loops in C

Co-authored by Sharon Ikechi

Write a program to display and then add all prime numbers between 1 and 100

This is a common assignment, test and exam question in Computer Science classes, to write a C program to list all prime numbers within a number range.

In this article, we’ll be breaking down how to approach such a challenge, so it’s easy to solve.

Before we begin, you might want to check this explanation out, if you’re uncomfortable with C syntax. It’ll help make this smoother.

The simplest C program, explained in detail

What are Prime Numbers?

First, they’re called Prime Numbers literally because they’re numbers “in their prime”. Like Prime Ministers, or Prime Beef, they exist above all other numbers, because:

Prime Numbers are integers that cannot be divided without remainders by any other integer besides 1 and themselves.

This means:

• the number 4, which can be divided by 1, 2 and 4 is NOT a prime number, while:
• the number 5, which can only be divided by 1 and 5 IS a prime number.
• the same goes for the number 13, 17 and 19, which ARE prime numbers.

Integers are just numbers that don’t have decimal points. E.g. 0, 2, 5, 100, are examples, while 3.5 is not.

The first 10 prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, so perhaps, we can write our C program as:

and it’d be correct.

But that’s probably not what your Lecturer expects, because the question might as well have been to display prime numbers between 1 and 1000, or up to 10,000, then what would you have done?

Introducing Loops

Loops are a way to do something over and over again till something happens.

If you’re a Nigerian, did you ever play or watch anyone play “tinko-tinko” as a child? Doesn’t matter if you haven’t, we got y’all …

tikonko-tinko … tinko … tinko 😁

The game would be played by repeating the hand movements till someone falters. Such a game is a classic example of a loop.

While Loop

In fact, the while loop is perhaps the perfect kind of loop for this. It reads like:

while <condition is true>, do something

For our tinko-tinko game, this would be:

while no player has faltered, do hand movement

For Loop

The for loop uses a numeric counter to keep score of how many times an action has to be repeated.

It looks like:

for (begin; repeat-condition; update) {
  // action
}

The begin statement sets the counter to a value.

The for loop will execute the action and update till the repeat-condition becomes false.

For the following:

for (int counter = 1; counter <= 5; counter++) {
  printf("%d\n", counter);
}

The loop starts with the counter variable set to 1, then prints out its value to the screen and increments it by 1, over and over again till the value of counter is 5.

Note: counter++ means to increase the value of counter by 1

Our Prime Number Solution

We’d have to check all integers (except 1) between the number range given, and make sure it cannot be divided by any positive integer (except 1) less than itself.

This means for the number range 1–10, we’d have to consider the numbers 2, 3, 4, 5, 6, 7, 8, 9, 10. To do this without repeating ourselves, we’d use a loops.

More exactly, we’d use a for-loop because we have a

• beginning: start at 2
• repeat-condition: if counter is less than or equal to 10
• update: increment by 1

for (int counter = 2; counter <= 10; counter++) {
  // action
}

Our action will be to make sure counter cannot be divided by any positive integer (except 1) less than itself. For this, we’d use another loop.

Yes, you can have a loop within a loop 😃

for (int counter = 2; counter <= 10; counter++) {
  for (int lower = 2; lower < counter; lower++) {
    // action
  }
}

Next, we’d need a way to know that the value of counter, cannot be divided by any value of lower. For this, we need something we like to call an indicator.

An indicator is anything you check for signs e.g. a traffic light showing green means you can pass.

Here, we’d have an indicator as an integer called isPrime. Its value would be 1, but if the counter number is NOT a prime, its value would become 0.

for (int counter = 2; counter <= 10; counter++) {
  int isPrime = 1;
  for (int lower = 2; lower < counter; lower++) {
    if (counter % lower == 0) {
      isPrime = 0;
      break;
    }
  }
  // check value of isPrime
}

Note that % is modulo which returns the remainder of a division.

If the division of counter by any value of lower does not produce a remainder, then counter is not a prime number.

E.g. 4 / 2 = 2 without a remainder, so 4 is NOT a prime number

Our C program for printing the prime numbers between 1 and 100 now becomes:

To extend the range’s upper limit, you can replace 100 with a higher integer like 1000, as you so wish.

Now, we add and display the sum

To do this, we’d create an integer variable to hold the sum. Its value would be set to zero (0).

When we find a prime number, we’ll add it to the sum variable. At the end of our loops, we’ll print sum to the screen.

Yaaay, we made it!

If you made it this far, we hope you understand more about prime numbers, integers, loops and conditions than you did when you began reading this.

We also hope you understand the thought process behind the final program.

A little challenge for your new-found knowledge of loops would be to write a C program that prints out all odd numbers between 1 and 1000.

Ask your questions, and give feedback in the comments below.