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

에라토스테네스의 체

소수를 찾는 가장 빠르고 쉬운 방법

 

 

알고리즘

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

11^2 > 120 이므로 11보다 작은 수의 배수들만 지워도 소수를 모두 구할 수 있다

 

자바 코드

import java.util.*;

public class 에라토스테네스의체 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		//1 ~ n까지의 소수 찾기
		int n = sc.nextInt();
		
		//해당 index가 false면 index는 소수
		//n + 1인 이유 : 0부터 n까지 세야하기때문에 n + 1필요
		boolean[] prime = new boolean[n+1];
		
		//0과 1은 소수가 아니므로 true
		prime[0] = prime[1] = true;
		
		//n의 제곱근까지만 계산해도 배수를 다 지울 수 있음
		for(int i = 2; i <= Math.sqrt(n); i++) {
			//true이면 pass
			if(prime[i] == true) {
				continue;
			}
			//i*i 미만은 이미 처리 되었으므로 j의 시작값은 i*i로 최적화
			for(int j = i*i; j < prime.length; j = j += i) {
				prime[j] = true;
			}
		}
		
		//소수만 출력
		for(int i = 1; i <= n; i++) {
			if(prime[i] == false) {
				System.out.println(i);
			}
		}
	}
}

 

 

코드와 그림으로 이해하기 쉽게 설명해보자면

n이 13이라고 해보자

 

1. boolean[] prime = new boolean[14];

 

2. prime[0] = prime[1] = true;

 

3. for(int i = 2; i <= Math.sqrt(n); i++)

반복문 i가 3까지 ( 3*3 < 13 < 4*4 )

 

4. for(int j = i*i; j < prime.length; j = j += i)

i가 2일 때 j는 4, 6, 8, 10, 12 

 

5. for(int j = i*i; j < prime.length; j = j += i)

i가 3일때 j는 9, 12

이때 12는 이미 칠해져있으므로 continue

6. 반복문 종료

2, 3, 5, 7, 11, 13 출력

 

백준 관련 문제  1929 : 소수구하기

https://www.acmicpc.net/problem/1929

 

답 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int M = sc.nextInt();
		int N = sc.nextInt();
		
		boolean[] prime = new boolean[N + 1];
		
		prime[0] = prime[1] = true;
		
		for(int i = 2; i <= Math.sqrt(N); i++) {
			if(prime[i] == true) {
				continue;
			}
			for(int j = i*i; j < prime.length; j += i) {
				prime[j] = true;
			}
		}
		
		
		for(int i = M; i <= N; i++) {
			if(prime[i] == false) {
				System.out.println(i);
			}
		}
		
		sc.close();
	}
}

 

 

출처 : https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4