/**
  * Copyright (c): Uwe Schmidt, FH Wedel
  *
  * You may study, modify and distribute this source code
  * FOR NON-COMMERCIAL PURPOSES ONLY.
  * This copyright message has to remain unchanged.
  *
  * Note that this document is provided 'as is',
  * WITHOUT WARRANTY of any kind either expressed or implied.
  */

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

/* ---------------------------------------- */

typedef unsigned long int Nat0;

#define formatNat0     "%lu"
#define format10Nat0 "%10lu "

/* ---------------------------------------- */

typedef unsigned int Set;

#define SLEN (CHAR_BIT * sizeof (Set))

#define empty ((Set)0)
#define full (~empty)
#define single(i) ((Set)1 << (i))

/* ---------------------------------------- */

typedef Set * ArrayOfSets;

/* dangerous macros !!! */

#define remove(s, e) (s[(e) / SLEN] &= ~ single((e) % SLEN))
#define elem(e, s) ((s[(e) / SLEN] & single((e) % SLEN)) != 0)

/* ---------------------------------------- */

ArrayOfSets
mkField (Nat0 len)
{
  Nat0 setWords = (len + SLEN -1) / SLEN;
  ArrayOfSets res = malloc (setWords * sizeof (Set));

  if (!res)
    {
      perror ("mkField: can't allocate field");
      exit (1);
    }

  {
    Nat0 i;
    for (i = 0; i < setWords; ++i)
      res[i] = full;
  }

  return res;
}

/* ---------------------------------------- */

ArrayOfSets
sieveField (ArrayOfSets field, Nat0 len)
{
  Nat0 i;

  remove(field, 0);
  remove(field, 1);

  for (i = 2; i < len; ++i)
    if (elem(i, field))
      {
	Nat0 j;
	for (j = 2 * i; j < len; j += i)
	  remove(field, j);
      }

  return field;
}

/* ---------------------------------------- */

#define LL 100

void
writeField (ArrayOfSets field, Nat0 len)
{
  Nat0 i;
  for (i = 0; i < len; ++i) {

    if (i % LL == 0)
      printf(format10Nat0, i);

    printf (elem(i,field) ? "X" : ".");

    if (i % LL == LL -1)
      printf("\n");
  }
  printf("\n");
}

/* ---------------------------------------- */

int
main (int argc, char *argv[])
{

  Nat0 len;
  ArrayOfSets field;

  sscanf (argv[1], formatNat0, &len);
  field = mkField (len);

  writeField (sieveField (field, len), len);

  free (field);

  return 0;
}