자꾸 효율성 테스트에서 실패하여서 살짝 힌트를 봤다.
그랬더니 어떠한 소수의 제곱근 이하의 소수로 나누었을 때 나누어지지 않는다면 소수다.
라는 힌트를 받았다.

71로 제곱근을 계산해보면 8*8 ~ 9*9 사이니 8.xxxx가 나올 것이다.
8 이하의 소수는 2 3 5 7이 있다.
해당 4개의 소수로도 안 나누어진다면 그 숫자는 소수인 것이다.

class Solution {
    public int solution(int n) {
        int count = 0;
        for(int i = 2; i < n+1; i++){
            if(i % 2 == 0 && i != 2) continue;
            boolean ableDiv = false;
            for(int j = 2; j <= Math.sqrt(i); j++){
                if(i % j == 0){
                    ableDiv = true;
                    break;
                }
            }
            if(!ableDiv) count++;
        }
        return count;
    }
}

설명

• count : 소수의 갯수
• i : 자연수
• j : 제곱근 이하의 숫자만큼 반복
• ableDiv : 나눌 수 있는가 여부

if(i % j == 0){
	ableDiv = true;
	break;
}

• 제곱근 이하의 숫자 j를 돌면서 자연수를 j로 나누었을 때 나머지가 0 ( 나누어 떨어진다 ) 이라면
  ableDiv = true, 그 즉시 반복문 탈출

반복을 다 돌아도 나누어 떨어지는 숫자가 없다면 해당 숫자는 소수이므로 count++