소수 판별 (에라토스테네스의 체)

에라토스테네스의 체

---

에라토스테네스의 체 (위키)

  - 어떤 수가 소수인지 판별할 수 있는 방법

  - 2의 배수부터 지우고(자기자신 제외) 다음 숫자로 넘어가 3의 배수를 지우고(자기자신 제외)를 반복

  - 지운 숫자에 접근할 경우 다음 숫자로 넘어감

 

public int eratosthenes(int n){
    int[] arr = new int[n - 1]; // 0, 1 제외하고 n은 포함되어야 하니까 -1
    int count = 0;

    for(int i=2; i<=n; i++){
        arr[i - 2] = i;
    }
    
    for(int i=2; i<=n; i++){
        if (arr[i - 2] == 0){
            continue;
        }

        for(int j=i+i; j<=n; j+=i){ // 자기자신 제외 (i + i), 배수만큼 (j + i)
            arr[j - 2] = 0;
        }
    }

    for (int i : arr) {
        if (i != 0){
            count++;
        }
    }

    return count;
}