C Project: Prime Finder

What you will build

A prime number is an integer greater than 1 whose only positive divisors are 1 and itself. Trial division tests those divisors. This project prints every prime less than or equal to 50 and then prints how many there were.

Use stdbool.h for bool, true, and false. C has no built-in boolean type unless you include that header. Compile with Try it in C at/c/try — gcc.

Trial division

For a candidate n, try divisors from 2 upward. If any divisor splits n evenly,n is composite. You can stop when d * d > n: a larger factor would already have a matching smaller partner you would have seen.

#include <stdio.h>
#include <stdbool.h>

bool is_prime(int n) {
  if (n < 2) {
    return false;
  }
  for (int d = 2; d * d <= n; d++) {
    if (n % d == 0) {
      return false;
    }
  }
  return true;
}

int main(void) {
  printf("2: %s\n", is_prime(2) ? "prime" : "not");
  printf("9: %s\n", is_prime(9) ? "prime" : "not");
  printf("13: %s\n", is_prime(13) ? "prime" : "not");
  printf("1: %s\n", is_prime(1) ? "prime" : "not");
  return 0;
}

2 is prime. 9 fails because 3 divides it. 13 has no divisor with d * d <= 13 except trials that leave a remainder. 1 is not prime by definition.

List primes through 50

Loop n from 2 through 50. If is_prime(n) is true, print n and add one to a counter. After the loop, print the count. That pair of outputs is the project: the list and the total.

#include <stdio.h>
#include <stdbool.h>

bool is_prime(int n) {
  if (n < 2) {
    return false;
  }
  for (int d = 2; d * d <= n; d++) {
    if (n % d == 0) {
      return false;
    }
  }
  return true;
}

int main(void) {
  int count = 0;
  int limit = 50;

  printf("primes <= %d:\n", limit);
  for (int n = 2; n <= limit; n++) {
    if (is_prime(n)) {
      printf("%d ", n);
      count++;
    }
  }
  printf("\ncount: %d\n", count);
  return 0;
}

Check the list by hand

The primes at most 50 are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, and 47. Fifteen numbers. If your program prints 16, you likely treated 1 as prime. If it stops at 49, the loop used n < limitinstead of n <= limit — 47 would still appear, but a later limit that is itself prime would be dropped.

#include <stdio.h>
#include <stdbool.h>

bool is_prime(int n) {
  if (n < 2) {
    return false;
  }
  for (int d = 2; d * d <= n; d++) {
    if (n % d == 0) {
      return false;
    }
  }
  return true;
}

int main(void) {
  int expected[] = {2,  3,  5,  7,  11, 13, 17, 19,
                    23, 29, 31, 37, 41, 43, 47};
  int want = (int)(sizeof expected / sizeof expected[0]);
  int k = 0;

  for (int n = 2; n <= 50; n++) {
    if (is_prime(n)) {
      if (k >= want || n != expected[k]) {
        printf("mismatch at slot %d\n", k);
        return 1;
      }
      k++;
    }
  }
  printf("matched %d primes <= 50\n", k);
  return 0;
}

Why 2 is special

2 is the only even prime. After you know n is odd, you could trial only odd divisors. The simple loop from 2 is enough for a limit of 50 and stays easy to read. Do not start the divisor loop at 1:n % 1 is always 0, so every number would look composite.

#include <stdio.h>
#include <stdbool.h>

bool is_prime(int n) {
  if (n < 2) {
    return false;
  }
  if (n == 2) {
    return true;
  }
  if (n % 2 == 0) {
    return false;
  }
  for (int d = 3; d * d <= n; d += 2) {
    if (n % d == 0) {
      return false;
    }
  }
  return true;
}

int main(void) {
  int count = 0;
  for (int n = 2; n <= 50; n++) {
    if (is_prime(n)) {
      printf("%d ", n);
      count++;
    }
  }
  printf("\ncount: %d\n", count);
  return 0;
}

The printed list and the count must match the first full program. The even-skip is only a faster form of the same trial division.

Common mistakes

• Using bool without #include <stdbool.h>. That is not C++. Include the header or use int with 0 and 1.
• Testing divisors with d <= n. Then n % n == 0 marks every number composite. Stop at d * d <= n.
• Starting candidates at 0 or 1. Both are not prime.
• Using math.h and sqrt when d * d <= n already bounds the loop and needs no extra library.

Practice

1. Change the limit to 20, then to 100, and print both counts. For 20 the count is 8.
2. Print only the primes that are also one less than a multiple of 4 (5, 13, 17, …) within 50.
3. Write a second function that returns how many primes are at most limit, and call it from main instead of counting in the print loop.