에라토스테네스의 체

'에라토스테네스의 체'는 소수를 구할 수 있는 알고리즘이다.

에라토스테네스는 고대 그리스의 수학자 이름이고 체는 체에 거른다고 할 때의 그 체다.

이 알고리즘은 주어진 수의 배열에서 2의 배수를 삭제하고, 3의 배수를 삭제하고, 5의 배수를 삭제하고... 이걸 계속 반복해 소수만을 알 수 있게 하는 알고리즘이다.

 

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

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

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

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

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

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

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

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

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

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

 

위의 방법을 이용해 코드를 구현하면 된다.

public class Eratos {
	public static void main(String[] args) {
		// ArrayList로 구현
		ArrayList<Boolean> primeList;

		// 사용자로부터의 콘솔 입력
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();

		// n <= 1 일 때 종료
		if(n <= 1) return;

		// n+1만큼 할당
		primeList = new ArrayList<Boolean>(n+1);
		// 0번째와 1번째를 소수 아님으로 처리
		primeList.add(false);
		primeList.add(false);
		// 2~ n까지 소수로 설정
		for(int i=2; i<=n; i++ )
			primeList.add(i, true);

		// 2부터  ~ i*i <= n
		// 각각의 배수들을 지워간다.
		for(int i=2; (i*i)<=n; i++){
			if(primeList.get(i)){
				for(int j = i*i; j<=n; j+=i) primeList.set(j, false);
				//i*i 미만은 이미 처리되었으므로 j의 시작값은 i*i로 최적화할 수 있다.
			}
		}
		StringBuffer sb = new StringBuffer();
		sb.append("{");
		for(int i=0; i<=n; i++){
			if(primeList.get(i) == true){
				sb.append(i);
				sb.append(",");
			}
		}
		sb.setCharAt(sb.length()-1, '}');

		System.out.println(sb.toString());

	}
}

자바로 구현한 에라토스테네스의 체 알고리즘

 

단순 반복문으로 소수인지 확인하는 것보다 위 알고리즘을 사용하는 것이 속도가 더 빠르다!

function solution(n) {
    const arr = [];
    
    // 인덱스 번호가 주어진 숫자 n과 대응하도록 
		// 빈 배열을 만들고 원소는 true 값으로 채워준다.
  	// 여기서 true 는 소수라는 의미이다.
		// 배열은 0부터 시작하므로, 주어진 숫자 n에 1을 더해준다.
    for (let i = 0; i < n + 1; i += 1) {
        arr.push(true);
    }
    
    // 주어진 수의 제곱근까지만 계산해서 불필요한 반복을 최소화한다.
    // arr[i] 가 소수일 경우, 반복문을 진행한다.
    // 맨 처음 시작하는 2는 소수이므로,
    // 2를 제외한 2의 제곱부터, 제곱 값만 체크하여 지워나간다.
  	// 제곱근까지 반복한다.
    for (let i = 2; i * i <= n; i += 1) {
        console.log("i", i);
        if (arr[i]) {
            for (let j = i * i; j <= n; j += i) {
                console.log("j", j);
                arr[j] = false;
            }
        }
    }
    
  	// 0과 1은 소수가 아니므로 false 값으로 바꿔준다.
    arr.splice(0, 2, false, false);
    
    console.log(arr);

  	// 배열에서 true인 값만 걸러내고, true인 값의 개수를 출력한다.
    const result = arr.filter((value) => {
        return value !== false;
    })
    
    return result.length;
}

console.log(solution(50));

자바스크립트로 구현한 에라토스테네스의 체 알고리즘

 

============================================================================================

핵심은 주어진 배열크기만큼 모두 true(소수를 뜻함)로 만들어준 후,

2의 배수, 3의 배수, 5의 배수 등을 모두 false(소수가 아님)로 만들어 

true의 개수를 구하면 소수의 개수만을 구할 수가 있다!

 

출처

JavaScript__에라토스테네스의 체 구현 - 개발꿈나무의 개발로그