에라토스테네스의 체 > [200510] 소수 찾기 - 연습문제(level1)

1. 문제이해

- 1부터 n까지의 수 중 소수의 개수 구하기

 

2. 전략

- 에라토스테네스의 체 이용

1. 소수 여부를 나타내는 배열 생성
2. i의 배수에 해당하는 수 체크(i = 2)
3. i가 n의 제곱근일 때까지 반복(n의 제곱근 이상의 수가 소수가 아니라면 이미 앞에서 지워졌을 것!!)

- 개수는 n-1에서 시작해 소수 아닌 수 발견할 때마다 하나씩 감소시키기

 

3. 참고사항

- 에라토스테네스의 체의 마지막 조건은 n의 제곱근까지여도 된다!!(Math.sqrt(n) 이용)

- 심화 ver : 프로그래머스 소수찾기(완전탐색)

2020/09/18 - [Coding Test/프로그래머스] - ★[200918] 소수 찾기 - 완전탐색(level2)

- 다른 방법1 : n(or n의 제곱근)보다 작은 2와 홀수들과 나눴을 때 나누어 떨어지는 수가 없기 --> 시간복잡도 문제

- 다른 방법2 : n의 제곱근보다 작은 소수로 나누기(소수 캐시 관리 필요)

 

4. 코드

class Solution {
    public int solution(int n) {
        int answer = n-1; //1은 미리 제외
        boolean[] checklist = new boolean[n+1];
        for(int i = 2; i <= Math.sqrt(n); i++){
            if(!checklist[i]){
                for(int j = 2; i*j <= n; j++){
                    if(!checklist[i*j]){
                        checklist[i*j] = true;
                        answer--;
                    }
                }
            }
        }
        return answer;
    }
}