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

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

 

 

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

1978번: 소수 찾기

 

 

---

[1] 문제

 

 

 

 

 

 

---

[2] 정답 및 해석

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void) {

	int N;
	int i;
	int j;
	int a[100];
	int cnt = 0;

	scanf("%d", &N);

	for (i = 0; i < N; i++) {
		scanf("%d", &a[i]);
	}

	for (i = 0; i < N; i++) {
		for (j = 2; j <= a[i]; j++) {
			if (a[i] % j == 0) 
				if (a[i] == j) {
					cnt++;
					break;
				}
				else
					break;
		}
	}
	printf("%d", cnt);

	return 0;
}

 

scanf 를 통해 입력받은 값을 배열에 저장하고, 

다시 배열의 요소를 불러와서 소수인지 검사하는 방법으로 알고리즘을 짰다.

 

 

 

---

[3] 풀이 과정 및 오답

 

 

 

# 첫 번째 시도 - 오답

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void) {

	int N;
	int i;
	int j;
	int a[100];
	int cnt = 0;

	scanf("%d", &N);

	for (i = 0; i < N; i++) {
		scanf("%d", &a[i]);
	}

	for (i = 0; i < N; i++) {
		for (j = 2; j <= a[i]; j++) {
			if (a[i] % j == 0) {
				cnt = cnt + 1;
			}
		}
	}
	printf("%d", cnt);

	return 0;
}

 

위의 코드는 문제가 있다.

현재 코드는 모든 수에 대해 2부터 a[i]까지 나누어 보면서 나누어 떨어지는 경우 cnt를 증가시킨다.

그러나 이렇게 하면 소수가 아닌 수들도 여러 번 나누어지기 때문에 올바른 소수 판별이 이루어지지 않는다.
소수 판별 알고리즘은 개선되어야 한다...

 

 

 

---

[4] 정답 제출

 

 

고친 풀이로 제출한 결과 정답!

 

 

 

 

---

[5] 느낀 점

 

소수 판별 알고리즘은 자주 쓰이는 것 같다.

학교 전공 중에 '컴퓨터 알고리즘'이라는 수업을 듣는데 생각보다 수업 내용이 도움이 많이 됐다.

차분하게 단계적으로 생각하게 해준 것 같다.

for 문에서 i 변수를 사용할 때, 범위를 설정해주는 부분에서 실수가 잦다. 배열과 엮이니 더욱 헷갈린다.