[프로그래머스/자바]

 

import java.util.*;

class Solution {
    public int solution(int n) {
        List<Integer> list = new ArrayList<>();
        list.add(2);
        if(n==2){
            return 1;
        }else{
            for(int i=3;i<=n;i++){
                boolean check = false;
                for(int j=0;j<list.size();j++){
                    if(list.get(j)>Math.sqrt(i)){
                        break;
                    }
                    if(i%list.get(j)==0){
                        check=true;
                        break;
                    }
                }
                if(!check){
                    list.add(i);
                }
        }
        return list.size();
        }
        
    }
}

 

처음에는 밑에 코드를 생각하지 못했다.

 

if(list.get(j)>Math.sqrt(i)){
    break;
}

그러나 없이 실행하니 실행 시간도 오래 걸리고 시간초과가 나오는 예제도 있었다. 그러고나서 생각해보니 지난번에 풀었던 문제에서도 어차피 약수를 구할거 i의 제곱근까지만 계산을 하면되는구나 싶었다. 그래서 해당 코드를 추가해서 만약 i의 제곱근이하까지 나눠봤는데 안되면 이건 소수이다. 라고 하였다.

소수는 매번 2부터 나누는것이 아니라 list를 하나 만들어서 소수라고 계산되면 list에 추가하고, 그 list에 있는것들로 다시 다른 수를 나누는 방식으로 찾았다.