[백준] 2581번 : 소수 _ JAVA ( 주석 설명 )

1번

( ⌜1978번 : 소수 찾기⌟에서 사용한 방법 )

→ 제곱근을 이용한 소수 판별

: 입력받은 Num 이 '소수' 가 아닌 '합성수' 이면

Num = X * Y 에서 X 와 Y 중 적어도 하나는 Number 의 제곱근보다 작거나 같다

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


public class Main {

    //전체 시간 복잡도 : O(N(sqrt(N)))
    //전체 공간 복잡도 : 자료구조 x
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //빠른 실행을 위해 버퍼를 이용해 입력을 받는다.
        int start = Integer.parseInt(br.readLine()); //범위의 시작을 알리는 수
        int end = Integer.parseInt(br.readLine()); //범위의 끝을 알리는 수


        int prime_sum = 0; //범위 내의 소수들의 합을 나타내는 변수
        int prime_first = 0; //첫번째 소수(= 범위 내의 소수 중 최솟값)을 나타내는 변수

        for(int num=start;num<=end;++num){ //해당 범위에 있는 수 중 소수 찾기
            //소수 판별 함수 실행 => 소수일 때
            if(solve(num)){
                if(prime_first==0) { //prime_first가 초기값(=아무것도 들어가지 않는 상태)일 때
                    prime_first = num; //첫번째 소수 설정
                }
                prime_sum += num; //범위 내의 소수들의 합
            }
        }

        if(prime_first==0) //첫번째 소수(=범위 내의 소수)가 없을 때
            System.out.println(-1);
        else {
            System.out.println(prime_sum);
            System.out.println(prime_first);
        }
    }

    //시간 복잡도 : O(sqrt(N))
    //공간 복잡도 : 자료구조 x
    private static boolean solve(int num) {
        if(num==1) //1은 소수가 아니다.
            return false;

        else if(num==2) //소수 판별을 위해서 2부터 검사를 하니 num==2일 때는 따로 조건 처리를 해주어야 한다.
            return true;

        //sqrt(num) 이후 값부터는
        //1>나누어 떨어지지 않는 수이거나
        //2>나누어 떨어지되 sqrt(num) 이전 수를 약수로 가지고 있어
        //계산할 필요가 없다.
        for(int i=2;i<=Math.sqrt(num);++i){
            if(num%i==0) //1과 자기 자신을 제외한 수를 약수로 지니고 있을 때
                return false;
        }

        return true;
    }
}

 

---

 

2번

→ '에라토스테네스의 채'를 이용한 소수 판별

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


public class Main {
    public static boolean prime[];
    //전체 시간복잡도 : O(log(logN))
        //- 2,3,4... 각각의 배수를 범위 배열에서 지워가면서 진행한다.
            //이러한 시간 복잡도는 전체 N에서 (1/2+1/3+1/4...)의 시간이 소요되고, Sigma(1/n)을 적분하여, O(logN)의 시간복잡도를 가진다.
            //하지만 여기에서 합성수(4,6,8,9,10...)와 같은 경우는 이미 소수(2,3,5)의 배수에서 '소수가 아님'이 판정되었으므로 합성수의 배수는 따로 계산하지 않아도 된다.
            //따라서 소수들의 배수만 지워나가면 되며,
            //"가우스의 소수 정리" 로 인해 n번째 소수는 대략 1/ln(n) 을 이용해
            //Sigma ((1/n)*(1/ln(n)))을 적분한 값, O(log(log(N))의 시간복잡도를 가지게 된다.
    //전체 공간복잡도 : O(N)
        //입력받은 end 만큼의 배열 공간을 사용하므로, O(N)의 공간복잡도를 가지게 된다.
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //빠른 실행을 위해 버퍼를 이용해 입력을 받는다.
        int start = Integer.parseInt(br.readLine()); //범위의 시작을 알리는 수이다.
        int end = Integer.parseInt(br.readLine()); //범위의 끝을 알리는 수이다.

        //boolean 배열의 기본값은 false 이다.
        prime = new boolean[end+1];

        //소수 : false
        //합성수 : true
        solve(end);

        int prime_sum = 0;
        int prime_first = 0;

        for(int i=start;i<=end;++i){
            if(!prime[i]){ //소수일 때
                if(prime_first==0) //오름차순이므로, 첫번째 소수를 마주할 경우이다.
                    prime_first = i;
                prime_sum += i; //소수들을 전부 합한다.
            }
        }

        if(prime_first==0) //첫번째 소수(=범위 내의 소수)가 없을 때
            System.out.println(-1);

        else {
            System.out.println(prime_sum);
            System.out.println(prime_first);
        }
    }

    //시간복잡도 : O(log(logN))
    //공간복잡도 : O(N)
    private static void solve(int end) { //end 까지 소수 찾기
        //'1'은 소수가 아니다.
        prime[1] = true;

        for(int i=2;i<=Math.sqrt(end);++i){
            //해당하는 수가 이미 '합성수'로 판단이 나면, 그 배수는 이전 소수의 배수로 true 처리가 됐기 때문에 pass 해도 된다.
            if(prime[i])
                continue;

            //소수가 아닌 것들을 true 로 처리한다.
            //i*2는 2의 배수이므로, i=2일 때 모두 true 처리가 되었으므로
            //i*i부터 검사하는게 조금 더 효율적이다.
            for(int j=i*i;j<=end;j+=i){
                prime[j] = true;
            }
        }
    }
}