[Java] 에라토스테네스의 체 | 소수판별하기(isPrime) | 백준1929

방법 1.

	private static boolean isPrime(int n) {
		if (n == 1) {
			return false;
		}
		for (int i = 2; i < n; i++) { // 2부터 n-1까지
			if (n % i == 0) { // 한 번이라도 약수가 발견된다면
				return false;
			}
		}
		return true;
	}

시간복잡도 : O(n)

- n까지 모든 수를 다 돌며 약수여부인지 확인하기 때문에 시간복잡도는 O(n)을 가진다.

 

 

 

 

 

방법 2.

	private static boolean isPrime(int n) {
		if (n <= 1) {
			return false;
		}
		for (int i = 2; i <= Math.sqrt(n); i++) { // n의 제곱근 이하일 때
			if (n % i == 0) { // 한 번이라도 약수가 발견된다면
				return false;
			}
		}
		return true;
	}

시간복잡도: O(n^(1/2))

- 방법1을 개선하기 위하여, '모든 약수들은 대칭형태를 이룬다'는 점에서 착안하여 시간복잡도를 줄여보도록 하자.

- 즉, 8의 약수는 {1, 2, 4, 8} = {8, 4, 2, 1}와 같이 대칭 형태를 지닌다. 따라서 특정 숫자의 제곱근까지만 약수의 여부를 확인하면 된다. 8의 예시에서 {1, 2} 까지만 약수여부를 검증하여 소수인지 판별할 수 있다.

 

 

 

 

방법 3. 에라토스테네스의 체

 

시간복잡도: O(Nlog(logN))

 

- 방법1,2 에서와 같이 몇 개의 소수를 판별하는 게 아닌, 여러 개의 소수를 한꺼번에 판별하고자 한다면 ?

- 가장 먼저 소수를 판별할 범위만큼 배열을 할당해 그 인덱스에 해당하는 값을 넣어주고, 이후에 하나씩 지워나가는 방식

 

• (1) 이차원 배열을 생성해 값을 세팅한다. (인덱스 1번엔 값 1을, 인덱스 2에는 값 2를...)
• (2) 2부터 시작하여 특정 숫자의 배수를 지워준다. 단, 특정 숫자(= 자기 자신)은 남겨둔다.
  • 2부터 시작하는 이유? 1은 소수가 아니기 때문에 검사할 필요가 없다!
• (3) 3의 배수를 지운다.. 계속해서 반복
• (4) 이미 지워진 숫자의 경우 건너뛴다.
• (5) 2부터 시작하여 남아있는 숫자를 출력한다.

 

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

public class Main {

	static int[] a = new int[1000001];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());

		// M이상 N이하의 범위에서 증가하는 순서대로 순서를 출력한다
		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());

		// (1) 인덱스에 따른 값 세팅
		for (int i = 2; i <= N; i++) {
			a[i] = i;
		}

		// (2)(3)(4) 2부터 시작해서 특정 숫자의 배수를 지워나간다
		for (int i = 2; i <= N; i++) {
			if (a[i] == 0) { // 이미 지웠으면
				continue;
			}

			// (4) 아직 안 지웠으면
			// 특정 숫자의 배수부터 출발하여 가능한 모든 숫자를 다 지워준다
			for (int j = i + i; j <= N; j += i) {
				a[j] = 0;
			}
		}

		// (5) 남은 숫자들을 출력한다
		for (int i = M; i <= N; i++) {
			if (a[i] != 0) {
				bw.write(a[i] + "\n");
			}
		}
		bw.flush();
		bw.close();
	}

}