kingsubin

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

        for (int i = 2; i <= n; i++) { // 2부터 n까지의 소수
            boolean isTrue = true;
            for (int j = 2; j <= Math.sqrt(i); j++) { // 
                if (i % j == 0) {
                    isTrue = false;
                    break;
                }
            }
            if (isTrue) {
                count++;
            }
        }

        return count;
    }
}

- 실패

- n의 범위가 커서 O(n^2)으로 풀면 시간초과인데 방법 생각이 안남

- 찾아보니 소수 조건중 이런게 있어서 두번째 for문에서 j의 범위를 Math.sqrt로 제곱근으로 줄여 줬더니 통과했다.

 

* 소수 조건

자연수 n이 소수이기 위해서는 n이 n의 제곱근보다 작은 어떤 소수로도 나눠지지 않는다.