[C++] 소수의 개수 (에라토스테네스의 체)

📄문제

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

 

ℹ️ 조건

제한시간은 1초입니다.

 

⬇️ 입력

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

20

 

⬆️ 출력

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

8

 

📝 풀이

#include <iostream>

static bool isPrime[200001] = { false, };

int main()
{
	for (int i = 2; i < 200001; ++i)
		isPrime[i] = 1;

	for (int i = 2; i <= std::sqrt(200001); ++i)
		for (int j = i * 2; j < 200001; j += i)
			isPrime[j] = false;

	int N;
	scanf_s("%d", &N);

	int answer = 0;
	for (int i = 0; i <= N; ++i)
		if (isPrime[i])
			++answer;

	printf("%d", answer);
}

• 에라토스테네스의 체 알고리즘을 구현하여 해결하였습니다.