소수인지 판단할 때 시간 복잡도 줄이기

https://school.programmers.co.kr/learn/courses/30/lessons/92335

프로그래머스

위 문제를 풀 때 소수인지 판단하는 메소드를 다음과 같이 구현했었다. 그런데 시간 초과가 났다.

public boolean isPrime(long num) {
	for (int i = 2; i < num; i++) {
		if (num % i == 0) {
			return false;
		}
	}
	return true;
}

 

만약 100이 소수인지 판단한다고 가정하자. 100의 약수는 [1, 2, 4, 5, 10, 20, 25, 50, 100]이다. 이때 1부터 100까지 돌면서 약수인지 판단할 필요 없이, 100의 제곱근을 통해 구하면 더 효율적이다. 100의 제곱근인 10으로, 1부터 10 사이의 값만 돌면서 100으로 나눠떨어지는지? 즉, 약수인지 판단하면 된다. 따라서 제곱근을 구해주는 Math.sqrt() 메소드를 통해 다음과 같이 구현하면 된다.

public boolean isPrime(long num) {
	for (int i = 2; i <= Math.sqrt(num); i++) {
		if (num % i == 0) {
			return false;
		}
	}
	return true;
}