[프로그래머스] 소수 찾기 (Level.1)

문제 설명과 제한조건 

풀이

class Solution {
    public int solution(int n) {
        int answer = 1;
        int[] tmp = new int[n+1];
        for(int i = 0; i<=n; i++) tmp[i] = i;
        
        for(int i = 2 ; i <= n; i++){
            for(int j = i * 2 ; j <= n; j += i){
                tmp[j] = 0;
            }
        }
        for(int i = 3; i <=n; i++){
            if(tmp[i] != 0) answer++;
        }
        return answer;
    }
}

 

++

처음에는 시간 복잡도가 O(n^2) 으로 짰었다. 그랬더니 실행시간이 어마어마해지고 시간초과로 실패해서

다른 방법을 찾아봤다.

저 방법이 에라토스테네스의 체를 이용한거라나 뭐라나

 i의 배수들을 다 제외시키는 방법이었다.

그래서 조금이라도 시간을 더 줄이기 위해

class Solution {
    public int solution(int n) {
        int answer = 1;
        int[] tmp = new int[n+1];
        for(int i = 0; i<=n; i++) tmp[i] = i;
        
        for(int i = 2 ; i <= n/2; i++){
            for(int j = i * 2 ; j <= n; j += i){
                tmp[j] = 0;
            }
        }
        for(int i = 3; i <=n; i++){
            if(tmp[i] != 0) answer++;
        }
        return answer;
    }
}

n/2 까지만 반복문을 돌려봤는데 큰 차이는 안났다.