구름LEVEL 소수판별 코딩알고리즘 문제풀이

전에 접했던 구름 LEVEL 알고리즘 문제를 한번 풀어봤습니다.
원본 문제 URL은 아래와 같은데요. 쉬운 문제로 가벼운 준비운동인 셈입니다.
소수판별하는 문제 풀이이고 시간복잡도가 나오긴 하나 필수 통과요소로는 판단하지는 않는 듯 합니다.

level.goorm.io/exam/43238/%EC%86%8C%EC%88%98-%ED%8C%90%EB%B3%84/quiz/1

구름LEVEL

소수란 1과 자기 자신 외에는 약수가 없는 수인데요.
특정한 수 n이 소수인지 아닌지를 판별하는 알고리즘입니다.

특히 시간 복잡도 내에 통과할 것을 권장하는데요.
시간 복잡도 O ( √n ) 이 제시가 되었습니다. √는 '루트'라고 부르는데요.
제곱근을 구하는 수학 함수인데 수학용어를 끔찍히도 싫어하시는 분을 위해
아주 간단히 말씀드리면,

101 이라는 수가 소수인지 아닌지 판별하는 검사 횟수를
10번 약간 넘는 11번 정도로 제한하는 것을 의미합니다.
10 x 10은 100이니까 101과 거의 근사치이지요.

10007 도 소수입니다.
이 경우도 100x100은 10000 인데 101번 정도 검사하는 것으로
제한하는 것입니다.

다만 그 횟수를 막지는 않았고 권장하는 수준인 것이지요.
이렇게 적게 비교해서 과연 소수 판별이 가능할까요?
가능합니다 :)

101은 소수입니다. 101이 소수인지를 판별하려면
2부터 101까지 나누어 떨어지는지 비교할 필요가 없고,
2부터 11까지만 나누어 떨어지는지 판단하면 되는데요.

그 이유인즉은, 101을 11로 나누면 이미 9.18 이 되기 때문입니다.
즉 2부터 11까지 모두 나누어 보았는데도 나누어 떨어지는 숫자가 없기 때문에
그 이상 검사할 큰 숫자는 존재하지 않는다~ 라고 보는 것이지요.
그러니까 이 경우는 11까지만 비교하고 반복문을 종료, 다음 문장으로 이동합니다.

하지만 도중에 나누어 떨어지는 숫자가 존재한다면,
나누어 떨어지는 숫자가 원래 숫자n인 경우를 제외하고
소수가 아니라고 출력하고 끝나 버리지요.

10007의 경우도 2부터 101까지만 비교한 다음 101로 나눈 숫자는 대략 99.07이 되기 때문에
검사할 더 큰 숫자는 없다~라고 판단하고 반복문을 종료, 다음 문장으로 이동합니다.

O ( √n ) 의 비교를 거치고도 나누어 떨어진 숫자가 없어서 다음 문장으로 넘어온 경우라면
소수가 맞습니다.
소수가 맞다고 출력하고 끝나게 됩니다.

사실 제곱근을 구하고 몇가지 예외처리를 해도 이 문제는 풀릴순 있지만,
최대값이 유동적으로 점점 줄어드는 방식도 재미있을것 같아 색다른 방법으로 풀이를 해 보았습니다.

관련 소스는 C++이며 아래와 같습니다.

#include <iostream>
using namespace std;
int main() {
	int n, max;
	// 자연수 n을 입력받습니다.
	cin >> n;
	// 비교할 최대수치를 우선 n까지로 정합니다.
	max=n;	
	// 1은 약수가 아니므로 무조건 False를 출력하고 끝내버립니다
	// 이 후 반복문에서 예외처리를 할 필요가 없어 속도가 빠르기 때문입니다.
	if(n==1){ cout << "False" << endl; return 0; }
	
	// 2부터 최대값 max 까지 약수 검사를 위해
	// 반복문을 돌립니다.
	for(int i=2; i<=max; i++)
	{
		// 반복수 i가 초기입력수보다 작고 
		// i가 n보다 작고, n을 i 로 나눈 나머지가 0이면
		// 중간에 나누어지는 수가 있으므로 약수가 아니라고 판별하고 끝냅니다.
		if(i<n && n%i==0){ cout << "False" << endl; return 0; }
		// i가 반복을 진행할 최대 수치 max 를 조정합니다.
		// 만일 n이 2의 약수가 아니라면 n 까지 비교할 필요가 없습니다.
		// n/2까지만 비교하면 되며,
		// n의 3의 약수가 아니라면 n/3까지만 비교하면 됩니다.
		// 이런식으로 비교할 최대값의 크기가 점점 줄어든다면 처리 시간이 단축되고 시간복잡도 O(루트n)이 성립됩니다
		max=n/i;
		// cout << "max=" << max << endl;
	}
		
	// 앞에서 약수가 아님이 판별되고
	// 무사히 탈출했으면 True를 출력합니다.
	cout << "True" << endl;
	return 0;
}