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

 

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

1929번: 소수 구하기

소수구하기는 **에라토스테네스의 체** 알고리즘을 사용하여 구한다. 

 

에라토스테네스의 체는 전에 공부한적 있지만 좀 까먹어서 다시 공부한다. 

참고링크 

https://forward-movement.tistory.com/98

에라토스테네스의 체

에라토스테네스의 체 

대량의 소수를 구해야할 때 유용한 알고리즘 O(N^1/2)의 시간 복잡도를 가진다. 

 

1. 원리 

소수란 약수가 오직 1인수, 1을 제외한 수의 배수가 되는 수는 소수가 **아니다** 
==> 이러한 개념을 이용한 알고리즘 

임의의수 n까지의 소수를 구하고자 할 때 2부터 n 제곱근 까지 돌며 모든 배수들을 소수에서 제외시키는 방식 

N = 150 까지의 수 중 소수를 구한다고 하자 
2부터 150까지 배열에 모두 넣은 후 소수가 아닌것들을 모두 true로 체크하고 마지막에 체크가 안된 수들이 우리가 찾는 소수 

 

2. 구현 

1. 우선 N 까지의 소수를 구하고자 하면, n크기의 배열을 만든다. 

int arr[151] // 150 까지의 소수를 구하고자 할 때

1. 2는 소수이므로 그대로 두고, N 까지의 2의 배수들을 false로 치환한다. 
ex) 4,6,8...
2.  3은 소수이므로 그대로 두고, N까지의 3의 배수들을 false로 치환한다. 
3. 4는 2의 배수임으로 1번과정에서 false로 치환 됐으므로 넘긴다. 
4. 위의 과정을 N의 제곱근까지 반복한다. 

 

3. 백준 1929번 자바로 풀어보기 

import java.util.*;;
public class Main{
    //전역 변수 설정 
    public static boolean[] prime; //m과 n사이 배열 초기화 false로 만들어야하니까 boolean으로 정의
    public static void main(String[] args){ 
        
        //입력받고 
        Scanner in = new Scanner(System.in); 
        int M = in.nextInt();
        int N = in.nextInt(); 

        prime = new boolean[N+1]; 
        get_prime();

        for(int i=M; i<=N; i++){ 
            //false이면 
            if(!prime[i]) 
                System.out.println(i); 
        }
    }
        //에라토스테네스의 체 알고리즘 
        public static void get_prime(){ 
            //true = 소수아님, false 소수 
            prime[0] = prime[1] =true; 
            //'n'이 소수인지 판별하기 위해 '2'부터 'sqrt(n)'까지의 수만 검사하면된다. 
            for (int i=2; i<Math.sqrt(prime.length);i++){ 
                if(prime[i]) continue; //true 이면 패스 
                for(int j = i*i;j<prime.length;j+=i){ // i의 제곱부터 시작하는것은 이미 작은 배수들은 이전에 검사되어 'true'변경되었기 때문 
                    prime[j] = true;
                }
            }

        }
    }