[programmers] 소수 찾기 (java) -1level

문제 설명

 

 

문제 해결

 

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

 

문제를 보고 빠른 시간 안에 풀었다. 이중 for 문을 돌리면 어렵지 않다고 생각했기 때문이다.

하지만 결과는 시간 초과!

 

문제 해결 2

 

소수를 찾는 방법인 에라토스테네스의 체를 이용했다.  에라토스테네스의 체란 자기 자신을 제외한 배수의 수를 전부 지우는 방법이다.

코드를 보면 visited 방문 체크 배열을 생성해 배수들은 전부 소수에서 배제시켰다.

 

public class 소수찾기 {
    public int solution(int n) {
        int answer = 0;
        boolean visited[] = new boolean[n+1];
        for (int i = 2; i <= n; i++){
            if(visited[i]) continue; // 방문 했으면 지나가고

            for (int j = i+i; j <= n; j += i){ // n까지 돌리면서 자기자신을 제외하고 배수들을 true로 만들어준다.
                visited[j] = true;
            }
        }
        for (int i = 2; i <= n; i++){
            if(visited[i] == false) answer++;
        }
        return answer;
    }
}