[백준 1978번][C++] 백준 소수 찾기

www.acmicpc.net/problem/1978

1978번: 소수 찾기

문제

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

입력

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

출력

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

---

풀이

Algorithm

1. is_prime()함수 설명
   1. 우선 2를 제외한 짝수인 경우엔 2로 나누어지기 때문에 소수가 아니겠죠? 또한 1인 경우에도 소수가 아니기 때문에 이 수들을 모두 if문으로 먼저 처리해줍니다.
   2. 나머지 수들을 소수인지 판별하기 위해 자신의 루트 이하이면서 홀수인 수들로 차례로 나눠봅니다. 이때 나눠지는 것이 있으면 소수가 아닌거겠죠?
   3. 여기에서 자신의 루트 이하인 수까지만 나눠보는 이유는 n를 두 수의 곱으로 나타냈을 때, 무조건 한 수는 루트n보다 작거나 같을 수밖에 없기 때문이에요
   4. 이 모든 조건들을 통과한 수가 소수입니다.
2. N만큼 입력값을 받고, 그 수가 소수이면 count++을 해줘요
3. count를 출력하면 끝! 

 

code

#include <iostream>
#include <string>
using namespace std;

bool is_prime(int n) {
	if ((n <= 1 || n % 2 == 0) && n != 2) //2가 아니고 짝수이거나 1인 경우는 false
		return false;
	for (int i = 3; i * i <= n; i += 2) { //자신의 루트 이하이면서 홀수인 수로만 나눠보기
		if (n % i == 0)
			return false; //나누어지면 소수가 아님
	}
	return true;
}
int main() {
	int N, temp, count = 0;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> temp;
		if (is_prime(temp)) //소수인 경우 count++
			count++;
	}
	cout << count << '\n';
	return 0;
}