15. 소수의 개수

자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요.
만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다.
제한시간은 1초입니다.
▣ 입력설명
첫 줄에 자연수의 개수 N(2<=N<=200,000)이 주어집니다.
▣ 출력설명
첫 줄에 소수의 개수를 출력합니다.
▣ 입력예제 1
20
▣ 출력예제 1
8

#include
using namespace std;

int main() {

int n,i,flag,cnt=0,j;
cin>>n;

for(i=2;i<=n;i++){
	flag=1;
	for(j=2;j*j<=i;j++){ //j*j 하는 이유
						// ex) 20
						// 1 20
						// 2 10 
						// 4 5
						// 5 4 이후 숫자만 바 뀜
						 
		if(i%j==0){
			flag=0; //소수가 아닌것이 되면 break; 
			break;
		}
	}
	if(flag==1) cnt++;
}
cout<<cnt;
return 0;

}