/*
 * sieve.c
 * This program reads an number n and prints all the primes that are less
 * than (or equal to) n, using the Sieve of Eratosthenes.
 */

#include <stdio.h>

/* The maximal value for n we allow: */
#define MAX_NUM 1000

int main ()
{
  int     n;                      /* The input number. */
  char    is_valid [MAX_NUM + 1]; /* For each 2 <= k <= n: is k still valid.
                                     We define the array by the size of
                                     MAX_NUM + 1, as the first element has the
                                     index 0.
                                     We use char to save memory. */
  int     p;                      /* The current smallest valid number. */
  int     num_to_delete;          /* The number we wish to delete. */

  /* Read the input number. */
  printf ("Please enter an integer between 2 and %d: ", MAX_NUM);
  scanf ("%d", &n);

  if (n < 2 || n > MAX_NUM)
  {
    printf ("Invalid input!\n");
    return (1);
  }

  /* Make all numbers between 2 and n valid. */
  for (p = 2; p <= n; p++)
    is_valid[p] = 1;

  /* Go over all p values between 2 and n. */
  for (p = 2; p <= n; p++)
  {
    if (is_valid[p])
    {
      /* If p is still valid, then it is a prime - print it. */
      printf ("%d ", p);

      /* Delete all numbers: p, 2p, 3p, ... until n by making them invalid. */
      for (num_to_delete = p; num_to_delete <= n; num_to_delete += p)
        is_valid[num_to_delete] = 0;
    }
  }  
  printf ("\n");

  return (0);
}