큰 수의 소수 여부를 판단하기 위해 시간을 단축 시킨 코드를 구현하라.

int main(int argc, char** argv) {
	int num, cnt = 0;
	//freopen("input.txt", "rt", stdin);
	scanf("%d", &num);

	for(int i = 2; i <= num; ++i)
	{
		int flag = 1;
		for(int j = 2; j * j <= i; ++j)
		{			
			if(i % j == 0)
			{
				flag = 0;
			}			
		}
		if(flag == 1) cnt++;
	}
	
	printf("%d", cnt);
	
	return 0;
}