[알고리즘] 아리스토테네스의 체 (소수 구하기)

알고리즘 문제를 풀 때

정말정말 자주 쓰기 때문에 정리해봅니다.

---

 

1. 소수란?

자신과 1 이외의 정수로 나누어 떨어지지 않는 정수

 

2. 일반적인 소수 출력 코드

1000 이하의 정수 중 소수만 출력하게 작성된 코드이다.

class PrimeNum{
    public static void main(Stirng[] args){
        // 1은 소수가 아니므로 2부터 시작
        for(int n=2; n<=1000; n++){
            int i;
            for(i=2; i<n; i++){
                if(n%i==0)  // 나누어 떨어지면 소수가 아님
                    break;
            }
            if(n==i)        // 마지막까지 나누어 떨어지지 않음
                System.out.println(n);
        }
    }
}

1000 이하의 소수를 하나하나 소수인지 판별하게 된다.

첫번째 반복문은 1000이하의 수를 다 방문하도록 해준다.

이때 두번째 반복문을 통해 n이 소수인지 판별하게 된다.

n보다 작은 1이외의 수 중에 n과 나누어 떨어지는 수가 있다면

소수가 아닌 것이므로 반복문이 중단된다.

멈추지않고 반복문을 다 통과하게 된다면 소수로 판단하고 출력한다.

2. 아리스토테네스의 체

 

아리스토테네스의 체

2부터 N까지의 수 중에서 소수를 찾는다고 했을 때
N의 제곱근보다 작은 소수의 배수를 모두 지우고 남는 수는 모두 소수이다.

이 논리를 활용해 위의 그림처럼 N의 제곱근보다 작은 소수의 배수를 반복적으로 지우고

최종적으로 N이하의 소수만 남겨 소수를 구한다.

2-1. 알고리즘 순서

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.

2. 2는 소수이므로 오른쪽에 2를 쓴다.

3. 자기 자신을 제외한 2의 배수를 모두 지운다.

4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다.

5. 자기 자신을 제외한 3의 배수를 모두 지운다.

6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다.

7. 자기 자신을 제외한 5의 배수를 모두 지운다.

8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다.

9. 자기 자신을 제외한 7의 배수를 모두 지운다.

10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

2. 코드

public class Eratostenes {
    public static void main(String[] args) {
        boolean[] arr = new boolean[1001];    //true 이면 해당 인덱스 소수.
        arr[0] = arr[1] = false;
        for(int i=2; i<=1000; i+=1) {
            arr[i] = true;
        }
 
        //2 부터 숫자를 키워가며 배수들을 제외(false 할당)
        for(int i=2; i*i<=1000; i+=1) {
            for(int j=i*i; j<=1000; j+=i) {
                arr[j] = false;        //2를 제외한 2의 배수 false
            }
        }
        System.out.println("Prime number list from 2 to 1000 : ");
        for(int i=0; i<=1000; i+=1) {
            if(true == arr[i]) {
                System.out.print(i + " ");
            }
        }
    }
}

참고자료: 위키백과