[BAEKJOON] 1978번 : 소수 찾기

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

주어진 수들 중 소수의 개수를 출력한다.

예제 입력 1

4 1 3 5 7

예제 출력 1

3

 

 

---

풀이

소수 관련 문제는 에라토스테네스의 체를 사용하는 습관을 들여야겠다는 생각이 드는 문제였다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

코드

#include <iostream>
#include <math.h>
using namespace std;

bool Eratos(int n);


int main() {
	int n;
	cin >> n;

	int num, cnt = 0;
	
	for (int k = 0; k < n; k++) {
		cin >> num;
		if (Eratos(num))
			cnt++;
	}

	cout << cnt;

	
	return 0;
}

bool Eratos(int n)
{
	if (n <= 1) return false;

	bool* PrimeArray = new bool[n + 1];

	for (int i = 2; i <= n; i++)
		PrimeArray[i] = true;

	for (int i = 2; i <= sqrt(n); i++)
	{
		if (PrimeArray[i])
			for (int j = i * i; j <= n; j += i)
				PrimeArray[j] = false;
	}

	if (PrimeArray[n])
		return true;
	else
		return false;
	
}