[알고리즘] 에라토스테네스의 체

에라토스테네스의 체?

에라토스테네스의 체란 n까지의 소수를 찾는 알고리즘입니다.

소수를 찾는 알고리즘 중에 가장 빠른 방법입니다.

 

소수는 약수를 1과 자기 자신만 갖는 수를 말합니다.

 

n을 15라 가정하면

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

이렇게 2부터 15까지의 배열을 하나 만듭니다. (1은 소수가 아니기 때문에 2부터 합니다.)

그리고 각 수의 배수들을 지워줍니다. (본인은 지우지 않음)

그럼 2의 배수 3의 배수들을 지워 가다 끝까지 가면 지워지지 않은 남는 숫자들이 소수입니다.

 

import java.util.*;

public class Main {
	
	public int solution(int n) {
		
		int answer = 0;
		int [] ch = new int[n+1];
		
		for(int i = 2; i<=n; i++) {
			if(ch[i] == 0) {
				answer++;
				for(int j = i; j<=n; j = j+i) {
					ch[j] = 1;
				}
			}
		}
		
		return answer;
	}
	
	public static void main(String args[]) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		
		int n = kb.nextInt();
	
		System.out.print(T.solution(n));
	}
}

n까지의 소수의 개수를 알 수 있는 에라토스테네스의 체 코드입니다.

 

저는 수를 지워주는 것을 1로 바꿔주는 것으로 해봤습니다.

배열을 생성하면 0으로 다 초기화 되있기 때문에 그것을 1로 바꿔주면 0 값이 소수이기 때문에

answer++를 하여 개수를 확인해봤습니다.