[프로그래머스,Java] Level1: 소수 찾기

문제분석:

 

간단하게 1부터 n까지 소수인것을 판별해서 갯수를 반환해주는 문제다.

 

이 문제는 효율성을 포함하고있다. 

너무 쉽다 생각하고 코딩하다가 효율성에 막히게된다.

 

N이 엄청큰 수 100만이상의 소수라면, 

 

혹시, 그 N을 2부터 100만까지 나누어지는지 연산을 100만번 반복시키지않았는가?

이걸 N, N-1,N-2... 까지 계속 반복시키다보면 엄청난 연산이필요하다.

 

소수판별은 2부터 100만까지 검사할필요가없다.

 

에라토스테네스의 법칙인 N의 제곱근까지만 판별해도 소수인지 드러난다.  

예를들어, 소수 31을 판별하는데, 2, 3, 4, 5 까지만 판별해도된다.

 

 

문제풀이:

class Solution {
    public int solution(int n) {
        //소수이면 true 아니면 false
        boolean flag;
        int answer = 0;
        //에라토스테네스의 법칙: n의 제곱근이하만큼 2부터 반복해서 나누어 떨어지지않으면 소수.
        for(int i=2;i<=n;i++){ 
 
            flag=true;
            for(int j=2;j<=Math.sqrt(i);j++){
                //소수가 아니므로 flag를 false로 만들고 break;
                if(i%j==0){
                    flag=false;
                    break;
                }
            }
            // flag가 true면 소수값이므로, 값 추가
            if(flag==true){
                answer++;
            }
        }
 
        return answer;
    }
}