[C] 백준 1978번 소수 찾기

1. 문제이해

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

1978번: 소수 찾기

 

수의 개수와 숫자들을 입력받아, 해당 숫자들 중 소수가 몇개인지를 출력하는 알고리즘을 구현하는 것이 목표이다.

 

 

 

2. 문제풀이

 

문제 그대로, 숫자들을 입력받아, 그 중 소수의 개수를 출력하는 것이 목표이다.

여기서 소수란, 1과 자기 자신만을 약수로 가지는 수를 이야기한다.

따라서, 1보다 큰 수 중에서 1과 자기자신이 아닌 다른 숫자로 나누어지면,

그 수는 소수가 아닌 것이다. (이를 합성수라고한다.)

 

이 점에 착안하여, 해당 숫자를 1. 2부터 자기자신보다 작은 숫자까지 나누고,

2. 나누어떨어진다면 소수가 아닌것으로 판단하고, 

이러한 숫자들의 개수를 3. 전체 숫자들의 개수에서 빼주어,

소수의 개수를 구해주는 형식의 알고리즘을 택했다.

 

여기서 또 한가지 주의해야 할 점이 바로 '1'이다.

1은 소수도 합성수도 아닌 수 이므로,

문제에서 이야기 한 소수에도, 위에서 이야기한 합성수에도 해당이 되지 않는다.

따라서 if문을 통한 예외처리를 통해 따로 구현해야겠다고 생각했다.

 

 

 

3. 소스코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
	int num[100];	// 입력받은 숫자
	int not_prime_num = 0;	// 소수가 아닌 숫자의 갯수
	int i, j;
	int N;	// 수의 개수

	scanf("%d", &N);

	for (i = 0; i < N; i++) {
		scanf("%d", &num[i]);
	}
	
	for (i = 0; i < N; i++) {
		// 1은 소수가 아니므로 카운트
		if (num[i] == 1) {
			not_prime_num++;
			continue;
		}
		// 1과 자기자신 이외의 수로 나누어지면 소수가 아니므로 카운트
		for (j = 2; j < num[i]; j++) {
			if ((num[i] % j) == 0) {
				not_prime_num++;
				break;
			}
		}
	}
	// 전체 숫자의 개수 중 소수가 아닌 것의 개수 빼기
	printf("%d", (N - not_prime_num));

	return 0;
}

위에서 언급한것처럼, 숫자들을 입력받은 뒤,

전체 개수에서 소수가 아닌것의 개수를 빼주는 형식으로 코드를 작성했다.

우선, 1은 소수가 아니므로, 입력받은 숫자중에서 1이 있을 시,

not_prime_num(소수가 아닌 숫자)를 증감시켜주었다.

이후 1이 아닌 다른 숫자들은, 2부터 자기자신보다 1작은 수까지 나눠가며,

나누어지면 합성수이므로 not_prime_num을 증감시켜주고 해당 반복문을 종료했다.

이렇게 세어준 소수가 아닌 수의 개수를 전체 개수에서 빼주어 소수의 개수를 출력해주었다.

 

 

 

---

실버4 단계의 두 번째 문제이다. 🤭

이번 실버 4문제는 저번의 터렛 문제보다 쉬웠지만.. 다음엔 또 어떤 어려운 문제를 풀게 될지..

한편으론 걱정스럽고, 한편으로는 기대되기도 한다.

파이썬은 꾸준히 공부중이긴 한데, 아직까지는 조금 어렵다.😥

주로 쓰는 언어는 C, C++, JAVA인데, 조만간 자바로도 풀이를 해서 올려봐야겠다!