// N의 값이 2이상의 수로 나누어 떨어지면 소수가 아님을 이용
class Solution {
    public int solution(int N) {
        int cnt = 0;
        
        // 2,3은 소수이기 때문에 제외함
        for(int num = 4; num<=N; num++){
// N = x*y일때 x,y는 x ≤ √N ≤ y임을 이용하여 √N까지만 반복함으로써 시간복잡도를 줄인다.
            for(int i = 2; i<=Math.sqrt(num); i++){
                if(num%i == 0) {
                    cnt++;
                    break;
// N이하의 수인 num가 합성수일경우 더 반복하지 않고 카운트 후 다음 num으로 넘어가 더 빠르게 처리한다.
                }
            }
        }
        
        return cnt;
    }
}

//다른 사람의 풀이중 참조할 코드를 적는다.