15. 소수의 개수

문제

자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요. 만약 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다. 제한시간은 1초입니다. 

입력설명

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

출력설명

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

입력예제

20

출력예제

8

---

#include <stdio.h>
using namespace std;

int main(){
	//freopen("input.txt", "rt", stdin);
	int n, i, j, count=0;
	bool flag;
	scanf("%d", &n);
	
	for(i=2; i<=n; i++){
		flag = true;
		for(j=2; j*j<=i; j++){
			if(i%j == 0){
				flag = false;
				break;
			}
		}
		if(flag == true) count++;
	}
	printf("%d", count);
	
	return 0;
}

이중for문을 사용해서 i=2; i<=n; i++해서 돌고 j=2; j*j<=i; j++ 하면 제곱근만큼 도는것과 같다.