1978: 소수 찾기

• toc {:toc}

문제

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

입력

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

출력

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

출처:https://www.acmicpc.net/problem/1978

풀이

1. 소수가 아닐 경우를 생각. > 약수를 가지고 있는 경우 대칭성을 띤다. i * i < N인 경우에서만 생각하면 됨.
2. 위의 경우에서 약수를 가지고 있지 않으면 소수가 됨.

#include <iostream>
 
using namespace std;
 
bool is_primeNum(int x);
 
int main()
{
	int N, x, num=0;
	cin >> N;
	for(int i=0; i<N; i++)
	{
		cin >> x;
		if(x == 1) continue;
		if(is_primeNum(x))
			num++;
	}
	cout << num << endl;
	
	return 0;
}
 
bool is_primeNum(int x)
{
	int i = 2;
	while(i*i<=x)
	{
		if(x%i==0)
			return false;
		i++;
	}
	return true;
}