[level1] 프로그래머스 - 소수 찾기(JAVA)

- 1~n까지의 모든 소수를 구하는 방법     => 에라토스테네스체 이용

(1) 1~n까지의 소수 유무를 저장할 배열을 만들고, 일단 모든 수를 소수라고 저장(true)

boolean[] Eratos = new boolean[n + 1];
Arrays.fill(Eratos, true);

(2) 2부터 자신이 소수이면, 자신으로 나누어 떨어지는 수는 소수가 아니므로 지움

for (int i = 2; i * i <= n; i++) {
	if (Eratos[i])
		for (int j = i * i; j <= n; j += i)		// 자신으로 나눌 수 있는 수 지우기
			Eratos[j] = false;
}​

 

- 이 과정을 i * i <=n 까지 반복하면 구하는 구간의 모든 소수만 남는다.(true)
        ㄴ 1~n 구간의 소수를 찾고 싶은 경우, t * t >n을 만족하는 t보다 작은 배수만 지워도 됨
             ex) 1~120이면, 11 * 11 >120 이므로,
                    11보다 작은 수 배수들만 처리해주면 됨

- t보다 작은 배수를 지우고 남은 수는 모두 소수!!​

 

 

import java.util.Arrays;

class Solution {
    public int solution(int n) {
        boolean[] Eratos = new boolean[n + 1];
        Arrays.fill(Eratos, true);
        for (int i = 2; i * i <= n; i++) {
            if (Eratos[i])
                for (int j = i * i; j <= n; j += i)
                    Eratos[j] = false;
        }

        int answer = 0;
        for (int i = 2; i <= n; i++)
            if (Eratos[i])
                answer++;

        return answer;
    }
}