소수 구하기

알고리즘을 공부할 겸 Hackerrank라는 곳에 가입해서 문제를 풀고있다.

웹에서 작성하면 자동으로 컴파일해주고 여러가지 value로 테스트도 진행해주기 때문에 

예외적인 상황에 대한 방어코드를 작성할 수 있게 해준다.

첫번째 문제는 소수 구하기였다.

n이 1과 자기외엔 약수가 없을 때 소수라고하는데 해당 로직을 구현하는 것은 어렵지 않았지만

테스트 도중 timeout이 걸렸고, 로직을 개선해야 했다.

처음엔 2부터 n까지 값을 증가시키며 나누어지는지 찾아나갔다.

for(int j=2;j<number;j++){
if(number%j == 0){
//소수가 아니다
isPrime = false;
break;
}else {
isPrime = true;
}
}

위 코드를 아래와 같이 개선하였다.

for(int j=2;j<=Math.sqrt(number);j++){
    if(number%j == 0){
//소수가 아니다
isPrime = false;
break;
}else {
isPrime = true;
}
}

n의 제곱근보다 작거나 같을때까지만 비교하면 됐다.

예를들면 n이 9일때 3까지만 비교한다.(9는 3의 제곱이므로)

n이 5라면 5의 제곱근인 2.23606보다 작거나 같을때까지만 비교하므로 3, 4일때 비교를 안해도 소수임을 알 수 있다.

소스는 아래 github에 올려두었다.

https://github.com/sungjaeHong/algorithm/blob/master/PrimeNumber.java