에라토스테네스의 체

 

소수를 구할 때 유용한 방식

시간 복잡도: O(NlogN)

 

1. 2부터 N까지의 수를 나열한다.

2. 2부터 가장 작은 수를 소수로 정하고, 2의 배수를 모두 지운다.

3. 지우지 않은 수 중에서 가장 작은 수(3)를 소수로 정하고 그 배수(3의 배수)를 지운다.

 

이렇게 하나씩 지워나가다 보면 지워지지 않는 수들이 있는데 이들이 바로 소수다.

 

 

public class Main {
	static boolean[] isPrime;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		// 2부터 구하고자하는 소수를 N까지 isPrime에 판별할 것이다.
		int N = Integer.parseInt(br.readLine());

		primeCheck(N);

	}


	// 해당 수끼지 소수에 대해 파악하기
	static void primeCheck(int N) {
		isPrime = new boolean[N + 1];
		
		for (int i = 0; i < N + 1; i++) {
			isPrime[i] = true;
		}

		// 0과 1은 소수가 될 수 없다.
		isPrime[0] = false;
		isPrime[1] = false;
		
		// 2부터 N의 제곱근까지의 모든 수를 확인
		for (int i = 2; i < Math.sqrt(N + 1); i++) {
			// 소수에 대하여 각각의 배수를 소수에서 제외해준다.
			
			if (isPrime[i]) { // 해당수가 소수라면, 해당 수를 제외한 배수들을 모두 false 처리하기
				for (int j = i * i; j < N + 1; j+= i) { // 그 이하의 수는 모두 검사했으므로 i * i부터 시작
					isPrime[j] = true;
				}
			}
		}
	}
}

 

 

일반적인 방식으로 구하고자 하는 입력값이 소수인지 판별할 때, 2부터 자기자신까지 나머지가 0인지 판별하는지로 판단한다면

시간복잡도: O(N^2)이므로 효율적인 방식이 필요하다.