[Lv.1] 소수 찾기 : Java

프로그래머스

 

 

 

이해하기

자신있던 소수 찾기 문제! 였지만 첫 번째 풀이에서 시간 초과 (런타임 에러) 를 마주했다 ㅋㅋ...

class Solution {
    public int solution(int n) {
        int answer = 0;

        for (int i = 2; i <= n; i++) {
            if (isPrime(i)) {
                answer++;
            }
        }

        return answer;
    }

    public boolean isPrime(int n) {
        if (n == 2) {
            return true;
        }

        for (int i = 2; i <= n / 2; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}

 

첫 번째 접근 방법은 아래와 같았다.

1. 2부터 n까지 for문을 돌린다.
2. i가 소수인지 확인한다.
   • 2는 소수이니 바로 return true해준다.
   • 아니라면 밑의 for문을 돌린다.
   • 2부터 n/2로 n을 나눠보면서, 하나라도 나누어 떨어지는 수가 있다면 false를 반환한다.
   • 아니라면 true를 반환한다.

여기서 시간 초과가 났던 부분은 ' 2부터 n/2로 n을 나눠본다.'였던 것 같다.

고민하다가 전에 다른 문제에서 Math.sqrt(n)까지만 소수 확인을 했던 것이 떠올라서 두 번째 풀이에 적용해보았다.

 

 

문제풀이

class Solution {
    public int solution(int n) {
        int answer = 0;

        for (int i = 2; i <= n; i++) {
            if (isPrime(i)) {
                answer++;
            }
        }

        return answer;
    }

    public boolean isPrime(int n) {
        if (n == 2) {
            return true;
        }

        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}

 

요거 하나만 고쳐주었는데도 바로 통과! 앞으로 소수 관련 문제가 나오면 Math.sqrt(n)까지만 확인해보도록 해야지...!