C Tutorial Lesson 2 – Writing a prime number generator

In this lesson we’re going to learn some of the most commonly used parts of the C language. We’ll cover enough ground to write a program that actually does something kind of useful.

We ended the previous tutorial with the following code:

#include <stdio.h>
int main(void)
{
 printf("Hello World");
 getchar();
 return 0;
}

Making a variable

In the program above, notice how the main function has the word int before it. int is short for integer. Because it is on the left hand side of the function name, it defines the type of the data that the function returns. We can see that the function ends with a return 0 statement. Zero is an integer. If we had written return “bye” instead, the compiler would have given us an error message when we pressed F5. In other words, the C compiler checks that the return type specified in the function definition is consistent with the value that the function returns.

We can also use int to declare a variable like this:

int i = 123;

This tells the compiler to reserve enough memory to hold an integer and to store the value 123 in that memory. With Visual Studio Express 2010, an int occupies 4 bytes of memory. That means it is 32 bits, which is enough space to represent any whole number from -2,147,483,648 to 2,147,483,647.

You can use printf with to print an integer like this:

printf(“%i”, i);

The %i asks printf to display the number as decimal. Try these combined like this:

#include <stdio.h>
int main(void)
{
  int i = 123;
  printf("%i", i);
  getchar();
  return 0;
}

Doing maths

Once we’ve got a variable, we can do all the usual maths things to it, like add another number etc. For example, you can write:

i = i + 1;

In the program:

#include <stdio.h>
int main(void)
{
  int i = 123;
  i = i + 2;
  printf("%i", i);
  getchar();
  return 0;
}

We call the + symbol an operator. Here’s a list of basic maths operators:

+ Plus
Minus
* Multiply
/ Divide (if two ints are divided, result will be an int)
% Remainder. eg 5%2 says divide 5 by 2 and find the remainder, which, in this case will be 1.

C also has shortcuts for simple modifications of a variable like this. Most C programmers would write the above as i += 2. You can use -= *= and /= too. Give it a try.

Another thing you will see a lot is i++ or i–. These mean “add one to i” and “minus one from i” respectively.

All these different forms will result in code of exactly the same efficiency. The compiler will automatically simplfy maths expressions to their simplest form, so you should just use whatever looks best. Normally people choose the shortest form.

The If Statement

The if statement lets you control which bits of your code are executed based on some condition statement. Here’s an example:

if (i <= 10)
  printf("i is less than 10");

You can add an else statement too:

if (i <= 10)
  printf("i is less than 10");
else
  printf("i is greater than 10");

The <= operator compares i to 10 and evaluates to true if i is less than or equal to 10. Other comparison operators you might want include:

< Less than
> Greater than
>= Greater than or equal to
== Equal
!= Not equal

The For Loop

One of the most useful features in C is the for loop. It lets you do execute the same instructions repeatedly. Here’s how to print all the numbers from 0 to 9 (C programmers always count starting at zero):

#include <stdio.h>
int main(void)
{
  for (int i = 0; i <= 10; i++)
    printf("%i ", i);
  getchar();
  return 0;
}

The for loop has three things inside the round brackets, separated by semicolons. Here’s what each part does:

  • The first part is executed once before the loop starts. In this case, the code we put in the first part was int i = 0 . Just like we have already seen, this declares a variable called i, initialized with the value zero.
  • The second part is executed once before each iteration of the loop. It’s just like the condition part of an if statement. The clever thing here is that if the code produces a value of zero, then the loop will stop. The code we wrote here, i <= 10, means that the loop will stop if i is less than or equal to 10.
  • The third part is executed once after each iteration of the loop. We wrote i++. We already know this means add one to i.

The final part of the for loop is the “body”. In this case the body is a single printf statement.

If you run this code you should see something like this:

lesson02-for-loop-output

Statements and Blocks

In our code above, if you want to put more than one line of code in the body of an if statement or for loop, you can use braces. ie, these fellas { }. Braces declare blocks. You can see how the main function already uses braces to declare its block of code. We can convert the for loop from having a single statement to using a block, like this:

#include <stdio.h>
int main(void)
{
  for (int i = 0; i <= 10; i++)
  {
    printf("%i ", i);
    i++;
  }
  getchar();
  return 0;
}

Give it a try.

Doing something kind of useful

We now have nearly enough knowledge to write a prime number generator. This is the kind of technology that would have made an Ancient Greek wet himself in excitement.

A simple prime number generator might use a for-loop to iterate through all the numbers you want to test for primeness. Lets start with the numbers 2 to 100.

#include <stdio.h>
int main(void)
{
  for (int i = 2; i <= 100; i++)
  {
  }
  getchar();
  return 0;
}

Now, we need to test each one of those numbers to see if it divides by any of the other numbers. If it does, it is not prime. So we need to put another for-loop inside the one we already have. The current loop uses the variable name i. The new loop will need to use a different name.

#include <stdio.h>
int main(void)
{
  for (int i = 2; i <= 100; i++)
  {
    for (int j = 0; ... ; j++) // Need to fill in the loop condition
    {
      // In here we will test if i / j is a whole number
    }
  }
  getchar();
  return 0;
}

I will leave it up to the reader to finish off this code. Good look.

Leave a comment