[C++][Baekjoon][Math] 1978번 소수찾기

[문제]

1978번: 소수 찾기

주어진 수 N개 중에서 소수가 몇 개인지 찾는 문제.

 

[풀이]

우선 소수란, 1보다 크며 1과 자기 자신 이외엔 나누어지지 않는 수를 말한다.

 

그리고 소수 찾는 법은 크게 2가지로 나뉜다.

1. 2부터 루트N까지 소수인지 아닌지를 판별하는 법. 시간복잡도 O(루트N).

2. 에라토스테네스의 체 방법을 이용하여 2부터 자신의 배수를 다 지우는 방법. 시간 복잡도 O(N(log(logN))).

 

1번 방법에서 루트N까지만 확인하는 이유는 그 이상은 루트N 이하의 배수이기 때문이다.

예를 들어 N으로 24가 주어지고 24의 약수는 1, 2, 3, 4, 6, 7, 12, 24가 있을 것이다. 그리고 24는 1*24, 2*12, 3*6, 4*6으로 약수의 곱으로 표현할 수 있다. 또한, 루트24 = 4.xx 이다. 즉, 4까지만 보면 그 이후는 4이하 수의 배수이므로 확인할 필요가 없는 것이다. 이 때, i <= 루트N 을 i^2 <= N 과 같음을 알아두자.

 

나는 1번 방법으로 2부터 루트N까지 소수인지를 판별했다. 이때 루트는 cmath 의 sqrt 함수를 사용했다.

 

참고로 pow(제곱근), sqrt(루트) 임을 알아두자.

 

[코드]

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

bool isDecimal(int num);

int main() {
	int num_count, num, sum = 0;

	cin >> num_count;
	for (int i = 0; i < num_count; i++) {
		cin >> num;
		if (isDecimal(num)) sum++;
	}
	cout << sum << "\n";
	
	return 0;
}

//소수: 1과 자기자신 외에는 나누어지지 않는 수
//pow(제곱근), sqrt(루트)
bool isDecimal(int num) {
	for (int i = 2; i <= sqrt(num); i++) {
		if(num%i == 0) return false;
	}
	return (num != 1) ? true : false;
}