20. 1929번 소수 구하기

에라토스테네스의 체를 이용한 소수를 구하는 문제이다.

*에라토스테네스의 체

출처 : 위키백과

2부터 2의 배수를 모두 제거한다. 이때 2는 제거하지않는다.

3부터 3의 배수를 모두 제거한다. 이때 3은 제거하지않는다. ...

 

각 숫자들의 배수들을 모두 제거하여 소수를 찾는 방식이다.

 

1. 입력받는 숫자들을 split으로 나눈다.

public class training {
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
		String[] split = br.readLine().split(" ");
		int a = Integer.parseInt(split[0]); 
		int b = Integer.parseInt(split[1]);
	}
}

 

2.소수 판별을 위한 배열 생성

boolean[] arr = new boolean[n+1];

 

3.숫자 0과 1은 소수에 포함되지 않으므로 처리

arr[0] = true;
arr[1] = true;

이때 true 값은 소수가 아닌것

 

 

4. 2부터 순차적으로 각배수들의 값을 true로 전환

		for(int i=2; i<=b;i++) {
			if(arr[i]==true) { 
				continue; 
			} 
			for(int j=i+i; j<=b; j=j+i) { 
				arr[j]=true; 
			} 
		}

첫번째 if는 true일경우 이미 소수가 아님을 판단 넘어간다.

탐색중인 수의 배수인 수도 모두 true만들어 주는데 단 이때는 최대값을 설정한 b의 값을 넘지는못한다

 

5. false = 소수값들을 출력

for( int i=a; i<=b; i++) { 
    if(arr[i]==false){ 
        System.out.println(i); 
    }
}

 

코드전문

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class training2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] string = br.readLine().split(" ");
        int a = Integer.parseInt(string[0]);
        int b = Integer.parseInt(string[1]);

        boolean[] arr = new boolean[b + 1];
        arr[0] = true;
        arr[1] = true;

        for (int i = 2; i <= b; i++) {
            if (arr[i] == true) {
                continue;
            }
            for (int j = i + i; j <= b; j = j + i) {
                arr[j] = true;
            }
        }
        for (int i = a; i <= b; i++) {
            if (arr[i] == false) {
                System.out.println(i);
            }
        }
    }
}

 

결과