← Previous Next →

Check If A Number Is Prime

A positive number is called a prime number if it is divisible only by 1 and by itself. 2, 3, 5, 7, 11, 13 are prime, while 4 (2 × 2), 6 (2 × 3), 8 (2 × 2 × 2), 10 (2 × 5), 12 (2 × 2 × 3) are not. There are infinitely many prime numbers, and being able to quickly check if a given number is prime, and if not, what its divisors are, is one of the important problems in the modern computer science.

Of course, we are not going that far. For now, we'll just write a basic check if a given number is prime. To check that, we'll look at the remainders of the division of that number by 2, 3, 4, ... – all the way to...

Stop here and think for a second. When do we stop checking? Let's look at two numbers: 25 and 29, and check if they are prime.

For 25, we check the remainders (operation %):

Let's look at 29:

but when do we stop? We could keep checking until 28, but do we need to? If we found that 29 is not divisible by 5, we need to check the next number 6, but notice: 6 × 6 is 36, which is greater than 29, so if we imagine that 29 is divisible by 6, the second divisor must be less than 6, but that means that we would've found it earlier when we checked 2, 3, 4, and 5.

So, we must exit the loop when we found a divisor (that means the number is prime), and keep checking until the number we check is less than or equal to the square root of the number, or, in other words, while (i * i <= n).

But what is i? Since we need to check if n is divisible by 2, 3, 4, etc., i must take all those values in a loop, one after one:

int n, i;

n = 25;  /* or whatever number we want to check */
i = 2;
while (i * i <= n) {
  ...   /* perform the check and break if true */
  ++i;  /* increment i by 1 */
}

I'll let you complete the code! Print prime if the number you read from the standard input is prime, and composite if it's not. I'll give you the read_int() function for now, you can scroll down through it and edit the code in main:

#include <ctype.h>
#include <stdio.h>

int read_int() {
	int result = 0;
	int c;

	while (isdigit(c = getchar())) {
		result = result * 10 + (c - '0');
	}

	return result;
}

int main() {
	int n = read_int();  /* read our number */

	/* write your while loop here! printf either "prime\n" or "composite\n" */

	printf("prime\n");

	return 0;
}

On the next page we'll discuss the technique you probably ended up using – the flag variable, and will also look at another way of writing loops in C: for loops. Keep reading!

← Previous Next →