/* primzahlen.c                                                        */
/* Das zweitaelteste Computerprogramm der Welt-: von anno -250.        */
/* Copyright: ERATOSTHENES, Philologe, Informatiker und Geograph       */
#include <stdio.h>

#define TRUE  1            /* Vorabdeklaration einiger Werte           */
#define FALSE 0
#define MAX   4000000

char flags[MAX];           /* Deklaration eines Arrays vom Typ char     */
/* Zuordnung: Der Zahl 2*i+3 entspricht der Eintrag flags[i]            */
/* Genauer: flags[i] == TRUE  <==>  2*i+3 ist prim                      */

int main() {
  int i, p = 2, k, size, count = 1;

  printf("Bestimmung aller Primzahlen bis (Zahl>=2) : ");
  scanf("%d", &size);
  size = (size+1)/2-2;

  for (i = 0; i <= size; i++)     /* Initialisiere das ...              */
    flags[i]=TRUE;                /* ... ganze Feld                     */

  for (i = 0; i <= size; i++) {
    if (flags[i]) {
      /* 2*i+3 ist prim, also streichen wir seine Vielfachen            */
      p = 2*i+3;
      count++;
      for (k=i+p; k<=size; k+=p)
        flags[k] = FALSE;
    }
  }
  printf("\n%d Primzahlen\n",count);
  printf("\nLetzte: %d\n",p);
}