[JAVA] 백준 1929번 소수 구하기 : 아리스토테네스의 체

1929번: 소수 구하기

 

1. 문제 추상화

 

M과 N 사이의 소수를 출력하시오.

 

2. 알고리즘

 

첫 번째 방법 ( % 연산 )

 

1. M부터 N까지의 자연수를 반복문 변수 i에 저장한다.

2. 이중 for문을 만들어, % 연산을 통해 소수여부를 판단한다.

3. 소수여부는 플래그 변수를 만들어 true, false로 파악한다.

 

 

두 번째 방법 ( 아리스토테네스의 체 )

 

1. N + 1 크기의 boolean 배열을 만든다. 

2. 이중 for문 구조를 만들어, 2의 배수, 3의 배수.... 를 true로 저장한다.

3. true로 걸러지지 않고 false 그대로 남은 수가 소수이다.

 

3. 코드

 

첫 번째 방법 ( StringBuilder 객체 사용 X )

 

%연산을 이용하여 문제를 풀었지만, StringBuilder 객체를 사용하지 않고 System.out.println()으로 소수가 발생할 때마다 출력해주었다. 반복적으로 출력이 이루어지기에 속도가 늦어진다.

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int M = sc.nextInt();
		int N = sc.nextInt();
		
		boolean isPrime = true; // 플래그 변수
		
        // M이 1과 0인 경우는 제외
		if(M == 1) {
			M += 1;
		}
		else if (M == 0) {
			M += 2;
		}
			
		for(int i = M; i <= N; i++) {
				for(int j = 2; j*j <= i; j++) {
					if( i%j == 0 ) {
						isPrime = false;
						break;
					}
				}
				if(isPrime) {
					System.out.println(i);
				}
				isPrime = true;
			
		}

	}

}

 

 

첫 번째 방법 ( StringBuilder 객체 사용 )

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {			
			Scanner sc = new Scanner(System.in);
			
			int N = sc.nextInt();
			int M = sc.nextInt();
			StringBuilder sb = new StringBuilder();
			
			boolean isPrime = true;
		
			if(N == 1) {
				N += 1;
			}
			else if (N == 0) {
				N += 2;
			}
				
			for(int i = N; i <= M; i++) {
					for(int j = 2; j*j <= i; j++) {
						if( i%j == 0 ) {
							isPrime = false;
							break;
						}
					}
					
					if(isPrime) {
						sb.append(i).append("\n"); // StringBuilder 객체 사용
					}
					isPrime = true;
			}
			
			System.out.println(sb);

		}

	}

 

 

두 번째 방법 ( 아리스토테네스의 체 )

 

아리스토테네스 체의 배열을 초기화할 때 for문의 구조가 특이하다. 

 

for(int i = 2; i*i < prime.length; i++) {
			if(prime[i]) continue;
			for(int j = i*i; j < prime.length; j += i) {
				prime[j] = true;
			}
		}

 

첫 번째 for 문 : for(int i = 2;  i*i < prime.length; i++) 

 

아리스토테네스 체는 소수의 배수를 걸러내는 체이다. prime.length가 10이라고 가정해보자. 그러면 i는 2와 3만 가능하다. 4부터는 제곱이 10보다 크다. 그러므로 2와 3의 배수만 true로 바뀐다.

 

1 2 3 4 5 6 7 8 9 10

 

2와 3의 배수만 걸러도 이처럼 소수가 드러난다. 

 

5의 배수

5x1

5x2

5x3

5x4 ( 5 x 2 x 2 )

5x5

5x6

.

.

5의 배수 중 5x5 밑은  2의 배수와 3의 배수로 이미 걸러진다. 그러므로 5 X 5 부터 가능한데, prime.length가 10이니 범위를 넘어선다. 그러므로 prime.length의 제곱근보다 큰 소수의 배수는 prime.length보다 크므로 반복문을 돌려줄 필요가 없다. 그래서 i*i < prime.length을 범위로 갖는다.

 

 

두  번째 for 문 : for(int j = i*i; j < prime.length; j += i)

 

두 번째 for문으로 들어온 i는 소수이다. 그리고 자기 자신보다 작은 수의 배수는 이미 이전 소수가 계산을 해놓았다.

 

5의 배수

5x1

5x2

5x3

5x4 ( 5 x 2 x 2 )

5x5

5x6

 

이미 2와 3의 배수가 

 

5x1

5x2

5x3

5x4 ( 5 x 2 x 2 ) 를 처리 했다.

 

그러므로 소수 5는 5x5부터 시작하면 된다. ( int j = i * i )  그리고 배수는 곱하기이자 더하기이기도 하다. 반복 하나가 끝나면 자기자신만큼 더해주면 된다. ( j += i )

 

그럼 코드를 살펴보자.

 

import java.util.Scanner;

public class Main2 {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int M = sc.nextInt();
		int N = sc.nextInt();
		StringBuilder sb = new StringBuilder();
		
		boolean[] prime = new boolean[N+1]; // 아리스토테네스의 체
		
		prime[0] = true;
		prime[1] = true;
		
        // 아리스토테네스의 체 초기화
		for(int i = 2; i*i < prime.length; i++) {
			if(prime[i]) continue;
			for(int j = i*i; j < prime.length; j += i) {
				prime[j] = true;
			}
		}
		
		for(int i = M; i<=N; i++) {
			if(!prime[i]) {
				sb.append(i).append("\n");
			}
		}
		System.out.println(sb);
	}

}

 

 

 

정리 

 

 

1. 두 번째 방법 ( 아리스토테네스의 체 + StringBuilder 객체 사용 )

2. 첫 번째 방법 ( StringBuilder 객체 사용 ) 

3. 첫 번째 방법 ( StringBuilder 객체 사용 X)

 

StringBuilder 객체를 사용하면 잦은 출력이 아닌 한번의 출력이 이루어지므로 빠르다. 그리고 아리스토테네스의 체는 소수의 배수들을 true로 걸러주면 인덱스가 올라갈수록 소수가 적어지므로 속도가 빠르다. 소수를 구하는 문제는 아리스토테네스 체를 웬만하면 이용하도록 하자.