[백준] 4948번

#include <iostream>
using namespace std;

int main(){
	int N;
	
	int i=0;
	int j=0;
	int count=0;
	bool prime[(123456*2)+1];
	
	
	while(1){
	
		cin>>N;
		if(N==0 || N>123456)
			return 0;
		
		
		for(i=0;i<=2*N;i++){
			prime[i]=1;
	}

	for(i=2;i<=2*N;i++){
		if(!prime[i])
			continue;
		
		for(j=i+i;j<=2*N;j+=i)
				prime[j]=false;
		
						

	}
	for(i=N+1;i<=2*N;i++){
		if(prime[i])
			count++;
	}
	cout<<count<<"\n";
		
	count=0;
	
	}
	return 0;
	
	
	
}