#include <stdio.h>

#define LIMIT 20000000

#define YES	1
#define NO	2
#define MAYBE	3

char primes[LIMIT];

int main ()
{
	int i, pos, nr = 0;
	primes[0] = NO; primes[1] = NO;
	for (i = 2; i < LIMIT; ++i)
		primes[i] = MAYBE;
	for (i = 2; i*i < LIMIT; ++i) {
		if (primes[i] != MAYBE)
			continue;
		primes[i] = YES;
		nr ++;
		for (pos = (i << 1); pos < LIMIT; pos += i) {
			primes[pos] = NO;
		}
	}
	for (; i<LIMIT; ++i) {
		if (primes[i] == MAYBE) {
			primes[i] = YES;
			nr++;
		}
	}
	printf ("Es gibt %d Primzahlen < %d\n", nr, LIMIT);
#ifdef OUTPUT
	{
		int count = 0;
		for (i=0; i<LIMIT; ++i) {
			if (primes[i]) {
				printf ("%8d", i);
				count++;
				if (count == 7) {
					count = 0;
					printf ("\n");
				}
			}
		}
	}
#endif
	return 0;
}