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

문제 이해하기

소수 찾는 방법을 알고 이를 적용하면 풀 수 있다. 입력한 n개의 자연수에 대해 각각 소수인지 점검하고 소수라면 이를 카운트한다.

 

코드로 표현하기

#include <iostream>

using namespace std;

bool isit(int x) { //소수 점검
	if (x == 1) return false;
	for (int i = 2; i < x; i++) {
		if (x % i == 0) return false;
	}
	return true;

}

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

	int num;
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		cin >> num;
		if (isit(num)) cnt++;
	}
	cout << cnt;
}

소수인지 점검하여 boolean타입으로 결과를 출력하는 함수 isit을 정의하고 이에 입력한 n개의 자연수 각각을 인자로 주어 소수 여부를 확인, 소수라면 cnt값을 1개씩 더하여 결과를 출력한다.

 

소수 찾기 알고리즘: 소수 n이 1과 자기자신(n)으로만 나누어짐->2부터 (n-1)까지의 자연수로 나누어지지 않음->2부터 (n-1)까지의 자연수로 나누었을 때 모두 0이 아닌 나머지 발생