에라토스테네스 : 소수만 걸러져라 (탈탈탈)

📖 에라토스테네스의 체란?

'에라토스테네스의 체'는 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법이다.

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

1) 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2) 2는 소수이므로 소수 리스트에 2를 추가한다.
3) 자기 자신을 제외한 2의 배수를 모두 지운다.
4) 남아있는 수 가운데 3은 소수이므로 소수 리스트에 3을 추가한다.
5) 자기 자신을 제외한 3의 배수를 모두 지운다.
6) 남아있는 수 가운데 5는 소수이므로 소수 리스트에 5를 추가한다.
7) 자기 자신을 제외한 5의 배수를 모두 지운다.
8) 남아있는 수 가운데 7은 소수이므로 소수 리스트에 7을 추가한다.
9) 자기 자신을 제외한 7의 배수를 모두 지운다.
10) 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

🧠 2부터 시작해서 해당 수가 소수이면 소수 리스트에 추가하고,
그 수의 배수들은 소수가 아니므로 소수 후보에서 제외하는 알고리즘

🧠 2부터 N까지의 수 중에서 소수를 찾는다고 했을 때,
N의 제곱근(나누어 떨어지지 않는다면 N의 제곱근 보다 큰 자연수)보다 작은 소수의 배수를 모두 지우고 남는 수는 모두 소수

---

💻 에라토스테네스의 체 구현(자바)

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());

	}
}

에라토스테네스의 체를 사용하면 숫자 하나 하나 소수 여부를 판별하는 것보다 속도가 빠르다! 소수 판별이 필요할 때는 에라토스테네스의 체를 사용하자!

출처: 에라토스테네스의 체 - 위키백과