[C++] 백준 1929번 소수 구하기

1. 문제이해

1929번: 소수 구하기 (acmicpc.net)

1929번: 소수 구하기

 

자연수 M과 N이 주어졌을 때, M과 N 사이의 소수를 모두 출력하는 것이 목표이다.

 

 

 

2. 문제풀이

 

자연수 M과 N 사이의 소수들을 오름차순으로 출력하는 것이 목표이다.

이전에 입력받은 자연수들 중 소수의 개수를 출력하는 문제를 푼 적이 있는데,

그와 유사한 방법으로 풀이했더니 시간초과가 발생했다.

 

풀이한 첫 번째 방법은 다음과 같다.

for문을 통해, N부터 M까지의 수들을 2부터 자기자신 전까지 나누어보고,

그 중 나누어떨어지는 수가 있다면 1과 자기자신 이외에 약수가 있는 것이므로

소수가 아닌 것으로 판별하는 방식이었다.

위와 같은 방법은 N과 M의 범위가 1 ≤ M ≤ N ≤ 1,000,000 이기 때문에,

for문을 통해 마지막까지 연산을 해주게 되면 주어진 시간보다 더 많은 시간을 초래하기 때문에

백준에서는 시간초과가 발생한 것 같았다.

 

 

따라서 생각한 두 번째 방법은 다음과 같다.

 

 

제곱근 값(루트값)을 기준으로 삼는 것이다.

제곱근 값을 기준으로, 앞의 있는 수들과 뒤에 있는 수들은 서로 짝을 이루게 된다.

( 2 x 8 = 16, 1 x 16 = 16 )

따라서, 제곱근 값을 기준으로 앞에 있는 수들로 나눠진다면, 뒤에 있는 수들 또한 나눠지게 된다.

이렇듯 제곱근 값(루트값)을 기준으로 앞에 있는 수들만 검사해,

for문을 통해 검사해야 하는 범위를 절반으로 줄여 시간초과를 해결하는 방식을 채택했다.

 

아래 소스코드에는 첫번째, 두번째 방법을 이용한 코드 모두 기재해놓았다.

 

 

 

3. 소스코드

 

1. 첫 번째 방법 (시간초과)

#include <iostream>
using namespace std;

int main() {
	int M, N;
	int not_prime_num;

	cin >> M >> N;
	
	for (int i = M; i <= N; i++) {
		not_prime_num = 0;

		// 1은 소수가 아니므로 따로 count
		if (i == 1) {
			not_prime_num++;
			continue;
		}

		// 2부터 자기자신 전까지 나눠지는 수가 있다면 소수가 아님
		for (int j = 2; j < i; j++) {
			if (i % j == 0) {
				not_prime_num++;
				break;
			}
		}

		// 약수의 개수가 0개 = 소수이므로 출력
		if (not_prime_num == 0) {
			cout << i << endl;
		}
	}

	return 0;
}

첫 번째 방법, N부터 M까지의 수들을 2부터 자기자신 전까지 나누어보고,

그 중 나누어떨어지는 수가 있다면 1과 자기자신 이외에 약수가 있는 것이므로

소수가 아닌 것으로 판별 하는 방법을 이용한 코드이다.

 

not_prime_num 이라는 변수를 두어, 나누어 지는 수가 있다면

해당 i (N에서 M사이의 자연수) 번째의 not_prime_num 값을 증가시켜주었다.

이후, 안쪽의 for문이 끝나면 (자연수 i를 2부터 i - 1까지 나누어본 후)

not_prime_num 값이 0인지를 확인하고,

0이면 약수가 없는 것, 소수이므로 출력하고

0이 아니라면 소수가 아닌것으로 간주하고 출력하지 않았다.

 

1의 경우에는 따로 if문을 통해 소수가 아닌것으로 판단,

not_prime_num값을 증가시켜주고, 해당 값이 0이 아니므로 출력해주지 않았다.

 

위 방법은 백준에서는 시간초과가 발생한 코드로,

시간초과가 발생하지 않은 코드는 아래 방법을 이용한 코드와 같다.

 

 

2. 두 번째 방법 (성공)

#include <iostream>
#include <cmath>
using namespace std;

int main() {
	int M, N;
	int not_prime_num;
	int root;	// 제곱근
	cin >> M >> N;
	
	for (int i = M; i <= N; i++) {
		not_prime_num = 0;
		root = (int)sqrt(i);

		// 1은 소수가 아니므로 따로 count
		if (i == 1) {
			not_prime_num++;
			continue;
		}

		// 2부터 제곱근값 전까지 나눠지는 수가 있다면 소수가 아님
		for (int j = 2; j <= root; j++) {
			if (i % j == 0) {
				not_prime_num++;
				break;
			}
		}

		// 약수의 개수가 0개 = 소수이므로 출력
		if (not_prime_num == 0) {
			cout << i << '\n';	// endl 사용시 시간초과 발생
		}
	}

	return 0;
}

위 첫번째 방법을 이용한 코드에서

제곱근 값을 나타내는 변수(root)를 따로 설정하여 살짝 수정해주었다.

 

not_prime_num값이 i가 바뀔때마다 0으로 초기화될때,

root값 역시 i에 따라 달라지므로 초기화 했다.

이후, 안쪽의 for문을 통해 2부터 자기자신(i)전까지 나누어보는 것이 아닌,

2부터 제곱근 값(root)까지만 나누어보는 방법을 이용해

for문의 실행시간을 줄여 시간초과를 예방했다.

 

이후, 동일하게 root_prime_num 값이 0이면 해당 자연수를 출력해주었다.

(이때, endl을 사용하면 시간초과가 발생해 \n을 써주었더니 시간초과가 발생하지 않았다.)

 

 

---

이전에 풀었던 문제와 거의 비슷하다 생각하고 풀었다가 큰 코 다친 문제였다..😱

비슷하다 생각해도 풀이방법이 정말 천차만별인 것 같다.