C++) 백준 4134번: 다음 소수

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

4134번: 다음 소수

소수 판별 문제이다. 조금 헤맸는데 이건 방법론적인 문제라 이에 대해서는 아래에서 이야기하려 한다.

단순 소수 판별 문제에 시간을 너무 투자하는 것이 너무 아깝다고 생각 되어 1시간정도 고민해보다가 구글링을 해보았는데.. 이게 웬걸 C++ 풀이가 안나오는 것이었다. 그래서 조금 더 고민해보고 풀어서 내가 C++ 풀이를 올리자고 마음 먹었다.

 

< 접근 방식 1 - 실패(시간 초과) >

처음엔 일반적으로 반복문을 통하여 n까지 모두 돌리며 n이상의 소수를 찾으려고 했는데, 입력값을 보니 시간 초과가 나올 것 같은 느낌이 딱 왔다. 이제는 대충 무엇이 잘못된 풀이 방식인지는 알 것 같다.

그래도 다른 방법이 떠오른 건 아니어서 일단 해보기로 했다. 아니나 다를까 시간 초과.

 

< 접근 방식 2 - 성공 >

단계 별로 풀어보기에는 제목 밑에 힌트가 있어서 그걸 참고하기로 했다.

힌트는 '√N까지만 나눠서 소수를 판별하는 문제' 라고 적혀 있다. 이걸 보고도 한참 고민했다. 그리고 후회했다. 그냥 하나 예를 잡고 써볼 걸..

 

핵심은 이거다. 100을 예로 들면

1 * 100

2 * 50

4 * 25

5 * 20

10 * 10

20 * 5

25 * 4

50 * 2

100 * 1

이렇게 100의 약수인 두 수의 곱으로 나타낼 수 있는데, 잘 보면 10을 기준으로 위 아래는 동일한 수들로 이루어져 있다. 따라서 굳이 100까지 검사하지 않고 √N까지만 확인을 해주면 소수인지 아닌지 판별이 가능하다는 것.

 

아래는 코드이다.

 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

bool isPrimeNum(long long n)
{
for (int i = 2; i <= sqrt(n); i++) {
if (n % i == 0) {
return false;
}
}

return true;
}

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

int T;
cin >> T;

long long n;
for (int i = 0; i < T; i++) {
cin >> n;
if (n >= 0 && n <= 2)
cout << 2 << endl;
else if (n == 3)
cout << 3 << endl;
else {
while (!isPrimeNum(n))
n++;
cout << n << endl;
}
}

return 0;
}

 

나에게 하는 말 - 처음에는 참 거짓 판별을 위해 flag 변수를 썼는데, 굳이 그럴 필요 없을 땐 bool 자료형을 적극 이용해보도록 하자.