에라토스테네스의 체

에라토스테네스의 체

고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법

1. 1부터 소수를 구하고자 하는 구간(n)의 모든 수를 나열한다.
2. 일단 소수도, 합성수도 아닌 유일한 자연수 1을 제거한다.
3. 2를 제외한 2의 배수를 제거한다.
4. 3을 제외한 3의 배수를 제거한다.
5. 4는 2의 배수이므로 넘어간다.
6. 이렇게 루트n 까지 반복한다.
7. 제거되지 않은 수들이 소수이다.

루트n까지 하는 이유는 n보다 작은 어떤 수 m이 m =ab라면 a와 b 중 적어도 하나는 루트n ​이하이다. 즉 n보다 작은 합성수 m은 루트n​보다 작은 수의 배수만 체크해도 전부 지워진다는 의미이므로, 루트n​ 이하의 수의 배수만 지우면 된다.

Java

import java.util.*;


/**
프로그래머스 12921 소수 찾기

크기가 n인 배열 arr 생성 후 1로 채운다.
arr[0]과 arr[1]은 0으로 변경 후
소수 m를 찾으면(arr[m] == 1) 해당 소수 m의 배수들을 배열 값을 1로 바꾼다.
마지막에 arr의 값이 1이면 소수임을 확인할 수 있다.
*/
class Solution {
    public int solution(int n) {
      int answer = 0;
      int[] arr = new int[n+1];      
      arr[0] = arr[1] = 0; 
      for (int i = 2; i <= n; i++) {  arr[i] = i;  }
 
      for (int i = 2; i <= (int)Math.sqrt(n); i++) {
         if(arr[i] == 0) continue; 
         for (int j = i+i ; j <= n; j+=i) {  arr[j] = 0; }
      }
      
      for (int i = 0; i < arr.length; i++) {
        if(arr[i] != 0) answer++;
      }
    
     return answer;
}
}