[C++] 백준 1929

백준의 1929번 문제 소수하기기 이다.

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

1929번: 소수 구하기

---

 < 문제 >

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

 

 < 예제 >

 

숫자의 범위를 입력받고 그 사이의 숫자들 중 소수를 전부 출력하는 문제이다.

2581번 문제 소수와 매우 유사한 문제이다.

https://loasd.tistory.com/44

[C++] 백준 2581

 

처음에 이 문제를 풀 때 기존의 방식을 사용하면 쉽다고 생각하여 코드를 작성했었다.

#include <iostream>
using namespace std;

int main() {

	int low_num, high_num;
	cin >> low_num >> high_num;

	int range = high_num - low_num + 1;
	int count = 0;
	for (int i = low_num; i <= high_num; i++) {
		for (int j = 2; j < i; j++) {
			if (i % j == 0) {
				count++;
			}
		}
		if (count == 0)
			cout << i << endl;

		count = 0;
	}
}

최소, 최대를 입력받았고 그 사이의 값들을 for문을 통해 2부터 해당 숫자까지 나누게 하였다.

예를들어 5, 16을 입력했다면 5부터 시작해서 5/2 -> 5/3 -> 5/4 이렇게 나눠서 0으로 떨어지면 count를 증가시켰고

나머지가 남는다면 소수인 것이기 떄문에 count가 0일경우 출력하게 하였다.

 

그러나 위의 코드를 실행시키면 Visual Studio에서는 제대로 작동을 하지만 정답 제출을 하면 시간초과가 뜬다.

그렇기 때문에 시간복잡도가 더 작은 방법을 택해야 했다.

그래서 아래의 방법을 택했다.

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int low_num, high_num;
	cin >> low_num >> high_num;

	int count = 0;
	for (int i = low_num; i <= high_num; i++) {
		if (i == 2 || i == 3) {
			cout << i << '\n';
		}
		else {
			for (int j = 2; j <= sqrt(i); j++) {
				if (i % j == 0)
					break;
				if (j == (int) sqrt(i))
					cout << i << '\n';
			}
		}
	}
}

제곱근을 사용하여 문제를 풀기로 했다.

간단히 설명하자면 이렇다.

예를들어 36이라는 숫자를 나눈다고 하면 √36 * √36을 기준으로 대칭을 이루게 된다.

 

2 * 18 | 3 * 12 | 4 * 9 | 6 * 6 | √36 * √36 | 6 * 6 | 9 * 4 | 12 * 3 | 18 * 2

 

이 방식을 사용하면 i%j를 했을 때 필요한 작업량이 절반으로 줄기 때문에 속도를 올릴 수 있다.

 

기존의 경우 i가 16이라면 16을 2 ~ 15로 나눠서 나머지가 있는 경우에는 소수가 아니라고 판단하게 하였는데

이런 방식으로 코드를 작성하다보니 시간이 많이 소요되었다.

그래서 제곱근을 사용한 코드는 다음과 같다.

for (int j = 2; j <= sqrt(i); j++) {
	if (i % j == 0)
		break;
	if (j == (int) sqrt(i))
		cout << i << '\n';
}

j < i 에서 j <= sqrt(i)로 바꾸었다.

이렇게 하면 작업의 양이 줄어들어 더 빠르게 결과를 도출해낸다.