소수 찾기

처음에 생각이 안나서 일단 원시적으로 해봤다.

class Solution {
    public int solution(int n) {
        int answer = 0;
        int count  =0;
        for(int i = 2 ; i<=n ;i++){
           for(int j = 1; j<=i ; j++){
               if(i%j==0){
                   count++;
               }
           }
            if(count<3){
                answer++;
            }
            count = 0;
        }
        return answer;
    }
}

결과는 시간초과, 뭐 그래도 결과가 나오긴 한다.

 

아리토스테네스의 체

요런놈을 발견했다. 한번 구현해보자