[C++] 백준 1978

백준의 1978번 문제 소수찾기이다.

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

1978번: 소수 찾기

---

 < 문제 >

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

 

 < 예제 >

 

테스트케이스의 갯수를 입력받고 그만큼 수를 입력받았을 때 소수가 몇개인지 찾는 문제이다.

 

일단 이 문제를 풀기 위해서는 소수가 무엇인지 알아야 한다.

소수란 1과 본인을 제외하고는 나누었을 때 값이 떨어지지 않는 숫자를 말한다. 또한 1은 소수가 아니다.

예제를 보면 1, 3, 5, 7에서 3, 5, 7은 무슨 수로 나누던 본인과 1을 제외하고는 값이 딱 떨어지지 않고 나머지가 남는다.

3의 경우 2로 나눌경우 나머지가 1이 남고 5의경우 2로 나눌경우 1, 3으로 나눌경우 2, 4로 나눌경우 1이 남는다.

 

그래서 소수를 찾기 위해 이러한 방식을 택하였다.

5가 입력되었다면 2부터 시작해서 5보다 낮은 4까지의 숫자로 나눈 값의 나머지가 0이 되는 값이 있다면 이 숫자는 소수가 아니다.

예를들어 8을 이런방식으로 탐색할 때 2로 나눌경우 나머지가 0이므로 이 숫자는 소수가 아니다.

반면 13을 2부터 시작해서 12까지 되는 수로 나눴을 때 나머지가 0이 되는 경우가 없다.

 

아래는 전체 코드이다.

#include <iostream>
using namespace std;

int main() {

	int t;
	cin >> t;
	int *num = new int[t];

	int prime_count = 0;
	int count = 0;
	for (int i = 0; i < t; i++) {
		cin >> num[i];
		for (int j = 2; j < num[i]; j++) {
			if (num[i] % j == 0) {
				count++;
			}
		}
		if (num[i] != 1 && count == 0) {
			prime_count++;
		}
		count = 0;
	}

	cout << prime_count;
	delete num;
}

먼저 테스트케이스의 갯수를 입력받고 이 크기에 맞는 배열을 생성해준다.

그 후 각각의 숫자를 입력받는다.

	for (int i = 0; i < t; i++) {
		cin >> num[i];
		for (int j = 2; j < num[i]; j++) {
			if (num[i] % j == 0) {
				count++;
			}
		}
		if (num[i] != 1 && count == 0) {
			prime_count++;
		}
		count = 0;
	}

이 부분이 소수의 갯수를 찾는 곳이다.

숫자를 입력받고 j가 2부터 시작되어서 나머지가 없는 값이 있을 경우 count가 1 증가한다.

전부 나눈 후 count가 0인 경우가 소수이며 1은 소수가 아니므로 if의 조건식을 채워준다.

 

그리고 마지막에 count를 0으로 초기화시켜주며 다음 숫자를 탐색할 수 있도록 한다.

 

 

기본적인 접근방법을 사용하여 소수를 구했는데 그 외에도 에라토스테네스의 접근 방법을 사용하면 더 빠르게 탐색할 수 있다.

 

에라토스테네시의 접근 방법에 대해서는 아래 링크의 블로그에 사진과 함께 자세히 설명되어 있어 따로 설명하지 않겠다.

https://ledgku.tistory.com/61

[소수 알고리즘] 소수의 특성과 에라토스테네스의 체