소수(Prime Number)인지 아닌지 확인하는 코드 JAVA로 구현하기

반응형

소수

소수는 1과 자기 자신만을 약수로 가지는 자연수를 의미한다.

사실 생각해보면 아주 간단하다.

 

하지만 이걸 막상 코드로 작성하려고하면 한 번 고민을 해봐야 한다.

 

N이라는 숫자가 소수인지 아닌지를 return하는 함수를 만든다고 가정해보자.

(1) 2 ~ N-1 을 싹 다 넣어서 약수인지 아닌지 확인하면 된다.

참고로 약수인지는 나눠서 나머지가 0이면 약수인 것이다.

하지만 이 과정은 너무 계산이 길다.

Big O 로 적으면 O(n)

 

이를 조금 줄여보자.

가장 쉽게 생각할 수 있는 방법은 절반을 나누는 방법이다.

 

하지만 한 번만 더 생각해도 정말 바보같은 생각임을 알 수 있다.

약수라는 것은 곱으로 이루어져있기에 말이다.

 

728x90

곱으로 이루어져있다는 아이디어를 활용하면 아주 간단해진다.

만약 N의 약수가 있다고 생각해자.

 

만약 N이 √N을 약수로 가지고 있다면? 

√N 이 N의 약수들 중에서 가운데 값일 것이다.

 

만약 N이 √N을 약수로 가지지 않는다면?

약수들 중 가운데 2개의 사에에 √N이 있을 것이다.

 

즉, 어떤 경우든 약수의 가운데에는 √N이 있다.

 

(2) 2 ~ √N 사이의 자연수들만 계산해보면 된다.

 

이걸 코드로 짜면

private static boolean isPrime(Integer num) {
	for(int i=2; i*i<=num;i++) {
		if(num%i == 0) {return false;}
	}
	return true;
}