문제 설명 2 이상 n 이하의 수 중에서 소수의 개수를 구하는 문제였다. 소수는 1과 자기 자신으로만 나누어지는 수를 의미하고, 1은 소수가 아니다. 풀이 설명 가장 기본적인 방법으로 2부터 n까지 모든 수를 검사하면서 소수 판별을 했다. 소수 판별은 2부터 해당 수의 제곱근까지만 나누어 떨어지는지 확인하면 된다. 나누어떨어지는 수가 하나라도 있다면 소수가 아니므로 false 처리하고, 아니면 소수로 간주해 개수를 증가시켰다. 제곱근까지만 확인하는 이유는, 예를 들어 어떤 수가 36이라면 6×6보다 큰 수들은 이미 작은 수와 짝을 이루어 확인되기 때문에 불필요한 연산을 줄일 수 있다.

class Solution {
    public int solution(int n) {
        // 소수의 개수
        int count = 0;
        // 2이상의 자연수만 소수가 될 수 있음 
        for(int i=2; i<=n; i++){
            boolean isPrime = true;
            // 소수 판별 : 2부터 해당수의 제곱근 까지의 수로 나누어 지지 않는 수 
            for(int j=2; j<=Math.sqrt(i); j++){
                // 나누어 떨어질 경우 소수가 아님
                if(i%j == 0){
                    isPrime = false;
                    break;
                }
            }
            // 소수라면 개수를 증가시킴 
            if(isPrime) count++;
        }
        return count;
    }
}

소수인지 판별하는 과정은 많은 문제들에서 사용되기 때문에 한 번쯤 알아두는게 좋다. 특히 "해당 수까지가 아니라 그 수의 제곱근까지만 비교하면 된다는 점" -> 이거 잊지 말기!