[알고리즘] 에라토스테네스의 체를 이용해 소수 구하기(JAVA)

소수(prime number)

1보다 큰 양의 정수 중에서 1과 자기 자신만으로 나누어 떨어지는 수를 말합니다.

 

에라토스테네스의 체

대표적인 소수 판별 알고리즘입니다.

1은 소수가 아니므로 2부터 소수를 구하려는 구간의 수를 모두 나열한 뒤

2의 배수부터 지워나가면 됩니다(2의 배수를 지운다면 자기 자신인 2는 지우지 않습니다)

 

---

 

1부터 50까지 소수 구하기

1. 2의 배수부터 지워나갑니다.(자기 자신은 지우지 않습니다)

 

2. 이미 지워진 숫자는 건너뛰고 3의 배수를 지웁니다.(자기 자신은 지우지 않습니다)

 

3. 위와 같은 방법을 반복해 지워나가면 소수만 남아있게 됩니다.

 

---

 

에라토스테네스의 체를 이용해 1부터 50까지의 소수 구하는 법을 JAVA 소스로 구현해보겠습니다.

package array;
 
public class PrimeNumber {
 
    public static void main(String[] args) {
        boolean[] primeNum = new boolean[101];
        primeNum[1] = true;
        
        for(int i=2; i<=50; i++) {
            for(int j=2; i*j<=50; j++) {
                primeNum[i*j] = true;
            }
        }
    
        for(int i=1; i<=50; i++) {
            if(!primeNum[i]) System.out.println(i);
        }
    }
}
 

먼저 boolean 함수를 이용해 참, 거짓을 나눠 소수가 아닌 것은 true로 판단하도록 했습니다.

 

1은 소수가 아니므로 true로 선언했고

 

이중 for문을 돌면서 i 배수가 되는 값을 true로 선언했습니다.

 

그 뒤 다시 for문을 돌면서 not 연산자 ! 를 이용해

 

primeNum[i] 반대의 값인 false를 뽑아냈고 이를 출력하도록 했습니다.