에라토스테네스의 체

• 에라토스테네스의 체 = 소수의 목록을 구하는

• 소수 = 나 말고는 나누어 떨어지는 수가 없는 것

• 배열에 포함되어 있는 숫자의 소수를 기준으로 배수가 되는 값이 있으면 배열에서 빼준다. (소수 제외)
  ex) 소수'2'를 제외한 모든 2의 배수 배열에서 지운다.

• 배수를 지울수록 나머지 연산을 해야하는 숫자가 점점 줄어들기 때문에 효율이 좋아진다. O(NlogN)

• 배수 빼지 않고 하나씩 다 나누는것은 O(N^2)

---

💻 첫번째 단계

// N = 50 미만의 모든 소수 구하는 에라토스테네스 채 알고리즘
public class RemoveMultipleOf {
    public static void main(String[] args) {

        // 1. 2~50까지 49칸 리스트 만들기
        List<Integer> numbers = new ArrayList<>();
        int N = 50;

        for (int i = 2; i < N; i++) numbers.add(i);

        // 2. 만든 리스트에서 2를 제외한 모든 2의 배수 지우기 -> j의 배수 지우기
        for (int i = 0; i < numbers.size(); i++) {
            for (int j = 2; j <= 7; j++) {
                if (numbers.get(i) % j == 0 && numbers.get(i) > j) {
                    numbers.remove(i);
                }
            }
        }
        System.out.println(numbers);
    }
    
}

---

💻 두번째 단계 - 완성

속도개선의 핵심
1 add(), remove() 하지 않는 것
2 % 나머지 연산을 하지 않는것

static int[] primeNumberSieve(int n) {
        int [] arr = new int [n+1]; // 숫자를 지울 배열
        // 1. 배열 초기화
        for (int i = 2; i <= n ; i++) {
            arr[i] = i;
        }
        // 2. 지우기
        for (int i = 2; i <= n; i++) {
            if(arr[i] == 0) continue; // 이미 지워진 수라면 건너뛰기

            for (int j = 2 * i; j <= n; j+=i) {
                arr[j] = 0;
            }
        }
        return arr;
    }

✔ 배열 초기화
array의 인덱스와 array의 vlaue가 같도록 배열을 생성 해 주었다. 그리고 소수에는 0,1이 포함 되지 않으므로 for문 초기값을 2로 지정해주었다.

---

✔ 지우기
이전 단계에서 지워진 소수의 배수들은 array[i]값이 0이 되어 있을 것이다. 따라서 0이면 다음 수를 점검할 수 있게 continue를 넣어주었다.

• 내부 반복문은 시작조건 2*i
  : 소수는 1과 자기자신을 약수로 가지는 수이기 때문에, 1 다음으로 소수가 될 수 있는 2와 점검할 값을 곱한 수 부터 점검을 시작해야한다.

• 내부 반복문의 종료조건 j+=i
  : i의 배수를 표현해 준것이다.

✔

i=2) j = 4,6,8,10,12,,,(+2)
i=3) j = 6,9,12,15,,,(+3)
i=4) continue
i=5) j = 10,15,20,25,,,(+5) 

---

✔ 결과값

arr =  [0, 0, 2, 3, 0, 5, 0, 7, 0, 0, 0, 11, 0, 13, 0, 0, 0, 17, 0, 19, 0, 0, 0, 23, 0, 0, 0, 0, 0, 29, 0, 31, 0, 0, 0, 0, 0, 37, 0, 0, 0, 41, 0, 43, 0, 0, 0, 47, 0, 0, 0, 0, 0, 53, 0, 0, 0, 0, 0, 59, 0, 61, 0, 0, 0, 0, 0, 67, 0, 0, 0, 71, 0 , ,,(생략)]

위 와같이 소수인 수만 남고 나머지 수들은 모두 0이 됐다.
코드를 변화하여 소수인 부분은 1 , 아닌 부분을 0 으로 해서 boolean형식으로 사용할 수도 있다.

---

⬛ 개선 사항 고려
바깥 반복문(for i)에서는 arr[i] == 0 일 때, continue 하는 코드를 넣어서 중복 점검을 방지 했는데 내부 반복문(for j)에서는 중복이 보인다.