[백준 BOJ] 1978번 소수 찾기 (C언어)

문제 설명

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

1978번: 소수 찾기

 

접근 방법 - 소수의 기본적인 정의에 대한 수학 문제

백준 1978번 문제는 소수의 기본적인 의미에 대해서 묻고 있는 수학적 사고력 문제이다.

어떤 숫자에 있어서, 나누어 떨어지는 숫자, 즉 약수가 1과 자기 자신 뿐인 숫자를 소수라고 부른다.

필자는 이 기본적인 정의에 중점으로 맞추어 문제를 해결해보려 하였다. 사실 노가다로 뛰어보았던 거지만

필자는 아래와 같은 순서로 코드를 작성하였고 문제를 해결하였다.

 

코드의 실행 순서

1) 입력받을 숫자의 개수와 이에 따른 임의의 숫자들을 입력받는다.

 

2) 정답을 저장하는 변수로, cnt를 0으로 초기화하면서 선언한다.

 

3) 반복문을 통해 1000까지의 자연수(i)를 모두 탐색해본다.

짝수는 소수의 정의에서 위배되기 때문에 조건문을 통해 바로 배제시킨다.

해당 i에 있어, 약수가 1과 자기 자신의 숫자인 i 뿐인지 다른 반복문을 통해 확인한다.

i가 소수가 맞다면 해당 숫자가 처음에 입력받은 숫자 중에 존재하는지 확인한다.

-> 모두 만족한다면 cnt에 1을 더한다.

 

4) 모든 반복문이 종료되면 cnt를 출력하면서 실행 종료한다.

 

후기

지인에게 듣기로, 원래 이 문제는 "에라토스테네스의 체"라는 알고리즘으로 풀어야 한다고 들었다.

하지만 이 개념에 대해서 당장 이해가 가지 않았던 필자는 우선은 노가다로 문제 해결을 하였고

그 결과로 너무 많은 반복문의 사용으로 인해 실행 시간이 다소 길게 나왔던 것으로 확인된다.

다음에 해당 알고리즘의 개념과 구현 방법을 확실히 깨닫고 나서는 이 문제를 다시 풀어보고자 한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <stdio.h>

//백준 1978번 코드
int arr[200];
int main() {
	int n;
	int count = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}

	for (int i = 2; i < 1000; i++) {
		if (i % 2 == 0 && i != 2) {
			continue;
		}
		int cnt = 0;
		for (int j = 3; j < i; j++) {
			if (i % j == 0) { cnt++; break; }
		}
		if (cnt != 0) { continue; }

		for (int j = 0; j < n; j++) {
			if (arr[j] == i) { count++; }
		}
	}
	printf("%d", count);
}

 

제출 결과

(2021.12.20 백준 1978번 제출 결과)

(이 글을 작성하고 있는 시점에선, 이전엔 버거웠었던 실버 문제를 간간히 풀어나가고 있다.

확실히 이제는 실버 문제에 익숙해졌다는 게 조금은 실감이 난다. 힘내야지.)