[BOJ / 백준] 1929번 소수 구하기 C++ 문제 풀이

단계별로 풀어보기 - 수학 2단계 - [3단계] 1929번

문제

문제 링크 : www.acmicpc.net/problem/1929

1929번: 소수 구하기

입력 복사 : 

3 16

 

CODE

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

int main() {
	int M, N;
	int rt;
	cin >> M >> N;

	for (int i = M; i <= N; i++) {
		rt = sqrt(i);
		if (rt == 1 && i != 1) {	//2,3인 경우
			cout << i << '\n';
			continue;
		}
		if (i % 2) {	//홀수일 경우
			for (int j = 2; j <= rt; j++) {
				if (!(i%j))
					break;
				if (j == rt) {
					cout << i << '\n';
				}
			}
		}
	}
}

 

풀이

이전 단계인 2581번에서의 코드를 조금만 변형한 다음과 같은 코드는 시간초과가 뜹니당...ㅠ

#include <iostream>
using namespace std;

int main() {
	int M, N;
	int cnt = 0;
	cin >> M >> N;

	for (int i = M; i <= N; i++) {
		for (int div = 1; div <= i; div++) {
			if (i%div == 0)
				cnt++;
		}
		if (cnt == 2) {		//i가 소수일 때
			printf("%d\n", i);
		}
		cnt = 0;
	}
}

위와 같은 코드에서는 범위로 주어진 M, N이 매우 큰 숫자라면 내부 for문이 범위내 모든 숫자에 대해 매번 돌아가는 것이 엄청난 시간을 소모할 것이다.

 

앞선 소수 구하기 문제들도 다음과 같은 방식으로 해결할 수 있고, 더 효율적인 코드입니다...!

 

우선 M과 N사이 각각의 숫자 i들이 소수인지 검사할 때, 해당 i의 제곱근까지만 검사합니다.

36 =	1 * 36	36 * 1
	2 * 18	18 * 2
	3 * 12	12 * 3
	4 * 9	9 * 4
	6 * 6

위 표와 같이 제곱근을 기준으로 제곱근이 아닌 인수들은 짝을 이루고 있기 때문에

제곱근까지만 검사를 해도 인수를 검출하여 소수임을 판단할 수 있습니다..!

 

		if (rt == 1 && i != 1) {	//2,3인 경우
			cout << i << '\n';
			continue;
		}

제곱근을 저장하는 변수 rt는 int형이기 때문에, 검사 중인 i가 1, 2, 3이라면 rt에는 1이 저장될 것입니다.

2와 3은 소수이기 때문에 출력하지만 1은 소수가 아니기 때문에 if문에 1을 제외시키는 조건을 넣습니다.

 

continue를 실행하면 나머지 반복 부분을 실행하지 않고 다음 i로 넘어가 반복문을 실행합니다.

 

		if (i % 2) {	//홀수일 경우
			for (int j = 2; j <= rt; j++) {
				if (!(i%j))
					break;

검사 중인 i가 짝수라면 2로 나눠지는 수이므로 소수가 아닙니다.

i가 홀수인 경우에만 i의 제곱근인 2부터 rt까지 검사하여, 나누어 떨어지는 인수 j가 있는 경우 소수가 아니라고 판단하여 검사하는 for문을 break로 탈출합니다.

 

결과