1978번: 소수 찾기

문제:

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

입력:

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

풀이:

• 소수는 자신과 1을 제외한 다른 약수가 없는 숫자이다. 따라서 이 문제를 풀기 위해서는 2부터 자기 자신까지의 숫자가 약수가 될 수 있나 확인해보면 된다. 하지만 그러면 시간 복잡도가 O(N)이니 조금 더 효율을 올리기 위해서 2부터 자기자신의 루트값까지만 하여 시간 복잡도를 O(N^1/2)로 만든다.
  • 이렇게 풀어도 상관이 없는 이유는 어짜피 루트값 전까지 아무 약수가 없다면 나머지 반에서도 약수가 나올 수 없기 때문이다. 예를들어, 18 같은 숫자를 보면 (1,18), (2,9), (3,6) 18의 약수는 서로 짝이 있어야 되는데 루트값을 넘길 때가지 없다는 것은 짝이 없다는 것이기 때문에 약수가 존재할 수가 없다.
• 만약에 약수를 발견했다면 isPrime을 false로 만들어 준 뒤 즉시 for문에서 탈출한다. 만약에 약수가 발견이 안됐다면 소수이므로 isPrime 초기 값이 true였기 때문에 그대로 answer값에 1을 더 해준다.

🔍 이 문제의 경우 구해야 되는 소수의 최대 개수가 1,000으로 적은 편에 속하고 시간도 넉넉하게 주어졌으므로 에라토스테네스의 체를 이용하지 않고 풀어도 괜찮다. 다만 개수가 많아질 경우에는 에라토스테네스의 체 알고리즘을 이용하는게 편하다. 이에 관해서는 #1929: 소수 구하기 문제에서 자세히 다루니 관심 있다면 한번 확인해 보는 것이 좋을 것 같다.

코드:

#include <iostream>
#include <math.h>

using namespace std;

int main(){
	bool isPrime;
	int n, answer = 0;
	//입력 
	cin >> n;
	for(int i = 0; i < n; i++){
		int temp;
		cin >> temp;
		isPrime = true; //false로 바뀌었을 수도 있는 isPrime값 true로 초기화
		//숫자의 루트 값까지의 모든 값이 배수가 될 수 있는지 확인 
		for(int j = 2; j <= (int)sqrt(temp); j++){
			//약수가 있는 경우(나누어 떨어지는 경우) 
			if(temp % j == 0){
				isPrime = false;
				break;
			}
		}
		//1은 소수가 아니므로 제외 
		if(temp!=1 && isPrime) answer++;
	}
	//출력 
	cout << answer;
}