15_소수의 개수.cpp

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

#include <iostream>
int array[200000];
int main() {
	
	int N,count=0;
	scanf("%d", &N);
	for (int i = 2; i <=N; i++)
	{
		for (int j = 1; j*i <= N ; j++)
		{
			array [ i * j]++;
		}
	}

	for (int i = 0; i <= N; i++)
	{
		if (array[i] == 1)
		{
			count++;
		}
	}

	printf("%d", count);
}

// *배열을 전역 변수에 설정하면 초기화 안해도 됨*
// 안하면 타임 리밋 뜸!