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

특정 범위에서의 모든 소수를 찾을때 가장 효율적인 알고리즘

⇒ 대량의 범위에서 소수를 찾을 때 가장 효율적인 방법인다.
⇒ 시간복잡도: O(N log long N)

예제) 2 ~ 120 까지의 모든 소수 찾기

과정

1. 2 ~ 120까지의 모든 숫자들을 나열합니다.

2. 2는 소수이므로 오른쪽에 2를 쓰고 2의 배수들을 모두 지웁니다. (빨간색)

3. 남아있는 숫자에서 3은 소수이므로 오른쪽에 3을 쓰고 3의 배수들을 모두 지웁니다. (초록색)

4. 남아있는 숫자에서 5는 소수이므로 오른쪽에 5를 쓰고 5의 배수들을 모두 지웁니다. (파란색)

5. 남아있는 숫자에서 7는 소수이므로 오른쪽에 7을 쓰고 7의 배수들을 모두 지웁니다. (노란색)

6. 위의 과정을 반복합니다.

7. 11 ×11 은 121 로 범위 2 ~ 120을 넘기 때문에 반복을 멈추고 남은 수(소수)들을 출력합니다.

위의 과정은 결국 120의 제곱근 이하인 소수의 배수만 제거해나가면 된다.
120의 제곱근은 10.954…이다. 즉 10이하의 소수들의 배수들까지만 지우면 남은 숫자들은 모두 소수가 된다.

코드(java)

• 범위 내 소수 여부 배열 구하기
  (해당 인덱스 값이 false 인 경우 소수이다.)

// 입력한 범위의 소수 여부(false인 경우 소수) 배열 구하기
public boolean[] getPrimeArray(int max) { // max = 구하고자 하는 범위
	boolean[] primeArray = new boolean[max+1];
	// 0,1 은 소수가 아니기에 제외
	primeArray[0] = true;
	primeArray[1] = true;

	// 범위의 제곱근 이하인 소수의 배수만 제거하면 남은 수는 모두 소수이다.
	for(int i=2; i<=Math.sqrt(max); i++) {
		// 소수가 아니면 pass
		if( primeArray[i] ) continue;

		// 소수의 제곱근 이후부터 소수 배수 제외
		for(int j=i*i; j<primeArray.length; j+=i) {
			primeArray[j] = true;
		}
	}

	return primeArray;
}

• 위의 식을 이용하여 특정 범위 내 소수 출력하기

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// 범위
    int max = sc.nextInt();
		// 범위가 1이면 소수가 없다.
    if(max <= 1) return;

		// 범위 내 소수 여부 배열
		boolean[] primeArray = getPrimeArray(max);
		// for문을 돌려서 여부 확인 후 출력
		for(int i=0; i<primeArray.length; i++) {
			// 해당 인덱스의 값이 false 인 경우 소수이다.
			if( !primeArray[i] ) {
				System.out.println(i);
			}
		}
	}
}

백준 - 소수 관련 문제
https://velog.io/@dayoung_sarah/백준-1978번-소수-찾기-JAVA
https://velog.io/@dayoung_sarah/백준-2581번-소수-JAVA
https://velog.io/@dayoung_sarah/17nbdduh
https://velog.io/@dayoung_sarah/백준-9020번-골드바흐의-추측-JAVA