/*
	Prime Number Generator by Sieve of Eratosthenes 
	@Author: md.moniruzzaman
*/

#include<stdio.h>
#define maxn 1000000

char Flag[maxn];
int Prime[79000], totalPrime;

void Sieve() {
	int i, j;
	for(i = 2; i*i<=maxn;) {
		for(j = i+i; j<=maxn; j+= i) {
			Flag[j] = 1;
		}
		for(++i; Flag[i]; i++);
	}
	Prime[0] = 2;
	totalPrime = 1;
	for(i = 3; i<maxn; i += 2) { // i+=2 ?? there is no consecutive prime except 2,3
		if(Flag[i] == 0) {
			Prime[totalPrime++] = i;
		}
	}
	
}

void PrintPrime() {
	int i;
	printf("Total prime numbers between 1 and 1000000 is: %d\n",totalPrime);
	for(i = 0; i<100; i++) { // printing 1st 100 primes
		printf("%d ",Prime[i]);
	}
	puts("");
}
void main() {
	Sieve();
	PrintPrime();
}