[프로그래머스] 소수찾기

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

효율성 테스트 실패

에라토스테네스 체를 이용해야한다.

 

1. Math.sqrt로 제곱근을 찾아내어

2. 2부터 제곱근 사이에 잇는 배수를 모두 없애주면 된다.

3. 그 나머지는 다 소수이다.

 

 

class Solution {
    public int solution(int n) {
        int answer = 0;
        boolean[] sosu=new boolean[n+1];
        int root=(int)Math.sqrt(n);
        
        for(int i=2; i<=n; i++){
            sosu[i]=true;
        }
        
        for(int i=2; i<=root; i++){
            if(sosu[i]==true){
                for(int j=i; j*i<=n; j++){
                    sosu[i*j]=false;
                }
            }
        }
        
          for(int i=2; i<=n; i++){
             if(sosu[i]==true)answer++;
            
        }
        
 return answer;
    }
       
}//solution