[백준 1929]-[수학]-[에라토스테네스의 체] - 소수 구하기 (java)

문제링크 : https://www.acmicpc.net/problem/1929

---

이 문제는 간단한 소수 구하기 소스로 구한다면 굉장히 오랜 시간이 걸리고 시간 초과가 발생하는 문제다. 

이문제의 입력되는 수의 범위는 1 ~ 1,000,000 인데 기존 소수 구하는 방식은 2 ~ N-1 까지 반복하면서 나누어 지는 수가 있는지 판단하는 소스 였다.

그럼 최악의 상황에서 1에서 1,000,000 까지 구해야 한다면  상상할 수 없는 연산 수가 발생한다. 

이렇게 큰 수들에도 소수가 있을거고 그럼 이 큰 수들을 소수인지 판별하는 방법도 있을것이다. 

그게 바로 에라토스테네스의 체 라는 방식인데 노가다라 비효율적인 방식이라고는 하는데 지금 문제에는 제일 적합한 방식이다. 

출처 : wiki 백과

에라토스테네스의 체를 구하는 방식은

2부터 ~ N까지  증가하는 i 를 제외한 i 의 배수를 하나하나 지워가면서 N까지 도달했을때 남은 수가 소수라고 하는 것이다. 

1 부터 120 까지의 수에서 소수를 구하는 예제 소스를 보자면 이렇다.

boolean[] primeNum = new boolean[121];
primeNum[1] = true;
        
for(int i= 2; i <= 120; i++) {
    for(int j = 2; i*j <= 120; j++) {
        primeNum[i*j] = true;
    }
}
        
for(int i=1; i <= 120; i++) {
    if(!primeNum[i]) System.out.println(i);
}

본인은 true 인것들은 소수가 아닌것으로 판단했다. 

1은 소수가 아니니깐 true로 하고 

2부터 120 까지 돌면서 i의 배수에 되는 인덱스에 true 로 값을 변경했다. 

결국 소수 인경우에는 false로 나오고 나중에 소수만 뽑아내고 싶으면 if(!primeNum[i]) 로  소수인지 판별하면 된다. 

이 문제를 풀때 먼저 입력받은 수만큼 에라토스테네스의 체로 소수를 구하고 

소수인 경우만 출력해주면 된다. 

소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static boolean[] primeNum;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int startNum = Integer.parseInt(st.nextToken());
        int endNum = Integer.parseInt(st.nextToken());
        
        primeNum = new boolean[endNum+1];
        getPrimeNum(); // 에라토스테네스의 체로 소수를 구한다.
        
        StringBuilder sb = new StringBuilder();
        for(int i = startNum; i <= endNum; i++) {
            if(!primeNum[i]) {
                sb.append(i + "\n");
            }
        }
        
        System.out.println(sb.toString());
        
        br.close();
    }
    
    public static void getPrimeNum() {
        primeNum[1] = true;
        
        for(int i= 2; i < primeNum.length; i++) {
            for(int j = 2; i*j < primeNum.length; j++) {
                primeNum[i*j] = true;
            }
        }
    }
}