프로그래머스 소수 찾기(java)

문제설명

생각하기

1. 약수를 통해 약수가 3이상인 수들을 제거하며 구할 수 있다.
2. 1번의 방법은 n이 커지면 커질 수록 시간이 많이 소요된다.
3. 에라토스테네스의 체를 사용한다.

내 풀이

에라토스테네스의 체는 각 수의 배수들은 소수가 될 수 없다는 것을 이용하여
수의 모든 배수들을 배제하고, 수를 증가시키고 반복하면 소수들만 남게 되는 공식이다.

먼저 era[]을 만들어 n+1만큼의 크기를 주고 2부터 n까지의 수를 모두 넣어준다.
2부터 n까지 0이 아니라면 j부터 n까지 0으로 만들어나간다.
이후 i를 증가시키며 반복한다.
마지막으로 era[]배열안에 0이 아닌 소수들을 세면 정답.