15. 소수의 개수 *

문제설명

자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요. 제한시간은 1초입니다.

입력설명

첫 줄에 자연수의 개수 N(2<=N<=200,000)이 주어집니다.

출력설명

첫 줄에 소수의 개수를 출력합니다.

시간 초과 코드

#include <iostream>
using namespace std;

int main()
{
	int n,cnt=0,flag;
	cin >> n;
	for (int i = 2; i <= n; i++)
	{
		flag = 1;
		for (int j = 2; j < i; j++)
		{
			if (i % j == 0)
			{
				flag = 0;
				break;
			}
		}
		if (flag == 1) cnt++;
	}
	cout << cnt;
	
}

#include <iostream>
using namespace std;

int main()
{
	int n,cnt=0,flag;
	cin >> n;
	for (int i = 2; i <= n; i++)
	{
		flag = 1;
		for (int j = 2; j*j <= i; j++) //수정 코드
		{
			if (i % j == 0)
			{
				flag = 0;
				break;
			}
		}
		if (flag == 1) cnt++;
	}
	cout << cnt;
	
}