[백준 알고리즘] 1929번 - 소수 구하기 (시간 초과, 소수 알고리즘)

1. 문제, 실행결과 예시

 

 백준 알고리즘 카테고리에 글을 쓰는게 정말 오랜만인 것처럼 느껴진다. 아마 실제로도 오랜만일 것이다 ㅎㅎ. 이 문제에 대한 풀이를 올리는 이유는 시간 초과라는 새로운 문제를 만났기 때문이다. 실제로 소수를 구하는 문제는 정말 많이 풀어봤지만, 이번 문제의 최대 입력값은 100000으로 기존에 사용하던 방법( 1 ~ N 까지의 모든 수를 비교하는 방법 )을 사용하면 시간초과가 날 수 밖에 없었다.( 심지어 숫자 하나당 줄바꿈을 해야하는 문제이다. ) 때문에 소수를 찾는 다른 방법을 사용해야 했다. 방법은 아래에서 자세히 설명할 것이다. 다음은 문제와 실행결과 예시 이다.

 

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

1978번: 소수 찾기

---

1978번 실행 예시

---

 소수를 찾는 방법은 정말 간단하지만, 시간 복잡도를 고려한다면 조금은 머리를 써야한다. 다음은 풀이과정이다.

 

2. 풀이 과정

 

이 문제에서 실행 시간 즉, 시간 복잡도를 고려하지 않는다면 다음과 같이 코드를 작성할 수 있을 것이다.

 

#include <stdio.h>
#include <math.h>

int main(void) {
	int min;
	int max;
	scanf("%d %d", &min, &max);

	for (int i = min; i < max + 1; i++) {
		int count = 0;
		for (int j = 2; j < i; j++) {
			if (i % j == 0)
				count++;
		}
		if (count == 0 && i != 1)
			printf("%d\n", i);
	}
	return 0;
}

 

 가장 기본적인 방법이다. 소수 여부의 판단 대상이되는 수를 N이라고 가정했을 때, 2 부터 (N - 1)까지의 수를 전부 N으로부터 나누고 결과가 0이 되는 수가 있으면 그 수는 소수가 아니라는 판별을 내리는 것이다. 그러나 말 그대로 모든 수를 나눠보는 방법이기에, 검사하려는 수들의 범위가 커지면 내부적으로 계사나는 횟수는 기하급수적으로 올라간다.

 

 따라서 계산을 조금이라도 줄일 수 있는 방법을 사용해야한다. 바로 루트연산자를 사용하는 것인데, 결론부터 말하면 2 부터 (N - 1) 까지의 수를 검사하지 않고, 2 부터 √N까지의 수만을 검사하면 된다. 원리는 다음과 같다.

 

 3. 원리 설명

 

 6의 약수를 수직선 위에 표시한다면 다음과 같을 것이다.

---

---

 빨간 중심을 기준으로 수들이 대칭인 것을 확인할 수 있다. 그리고 저 빨간 선의 값은 해당하는 수의 루트값이라는 것이다. 그럼 여기서 무엇을 알 수 있을까? 바로 저 빨간선 앞에 있는 수들 즉 (1 ~ √12)까지의 수들만을 나눠보고 나누어 떨어지는 값이 있으면 소수가 아니지만, 나누어 떨어지는 값이 없다면 소수인 것을 확인할 수 있다는 것이다. 왜냐하면 빨간선 뒤에 있는 수들은 앞에 대칭되는 수가 있어야 나누어 떨어지기 때문이다.

 

 위의 방식을 사용하여 코드를 작성하면 다음과 같다.

 

#include <stdio.h>
#include <math.h>

int main(void) {
	int min;
	int max;
	scanf("%d %d", &min, &max);

	for (int i = min; i < max + 1; i++) {
		int count = 0;
		int buff = (int)sqrt(i);
		for (int j = 2; j <= buff; j++) {
			if (i % j == 0)
				count++;
		}
		if (count == 0 && i != 1)
			printf("%d\n", i);
	}
	return 0;
}

 

 루트값을 구할 때는 sqrt() 함수를 사용하였다.

 

4. 결어

 

 백준알고리즘의 수학 카테고리에는 이런 문제들이 많은 것 같다. 단순하게 반복문만을 활용하지 않고 새로운 수식이나 방법들을 찾아야하는 문제들이 대부분이다. 다음에도 새로운 수식을 올렸으면 좋겠다.