/*=============================================================================
Filename: is_prime.c
Purpose : Function to test whether a number is prime
Author  : Tristan Miller -- psy@cs.toronto.edu

Study questions:
  * Why do we check only up to n / 2?  (line (a))
  * What is the running time of this program?
  * Is there a more efficient way to compute the first N primes?
=============================================================================*/

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define N 25

int is_prime(int n);

int is_prime(int n) {
  int i;

  for (i = 2; i <= n / 2; i++)    /* (a) */
    if (n % i == 0)
      return FALSE;

  return TRUE;
}

int main(void) {
  int i;

  for (i = 2; i < N; i++)
    if (is_prime(i))
      printf("%d is prime\n", i);
    else
      printf("%d is not prime\n", i);

  return EXIT_SUCCESS;
}