#include <iostream>
using namespace std;

int main() {
	// your code goes here
	int arr[1003003], i, j;							
	for(int k=0; k<1003003; k++) arr[k]=true;
	arr[0]=arr[1]=false;
	for(i=2; i*i<=1003003; i++) { 					
		if(!arr[i]) continue;					//doesnt execute the inner loop if "i" is
		for(j=i*i; j<=1003003; j=j+i) {			// false, or not prime
			arr[j]=false;		//all multiples of "i" are assigned "false", or not prime
		}
	}
	return 0;
}