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

1번

→ 기본적인 소수 판별

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

public class Main {
    static int count = 0; //입력 받은 수 중 전체적인 소수 개수

    //전체 시간 복잡도 : O(N^2)
    //전체 공간 복잡도 : 자료구조 x
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //빠른 실행을 위해 버퍼를 이용해 입력을 받는다.

        int N = Integer.parseInt(br.readLine()); //몇 개의 수를 입력받을지 정한다. //여기에서는 N을 사용하지 않으니 br.readLine()만 하고 넘어가도 된다.

        StringTokenizer st = new StringTokenizer(br.readLine());//" " 단위로 입력을 구분한다.

        //" "로 토크나이저의 문자열(토큰화한 문자열) 중에서 사용 가능한 토큰이 더 있는지 확인한다.
        //남아 있는 토큰이 있으면 true
        while(st.hasMoreTokens()){
            int num = Integer.parseInt(st.nextToken()); //다음 토큰을 num에 저장
            solve(num); //소수 판별 함수 실행
        }

        System.out.println(count); //소수 개수 출력
    }

    //시간 복잡도 : O(N)
    //공간 복잡도 : 자료구조 x
    //1부터 자기 자신까지, 전부 반복을 하므로 O(N)이 된다.
    private static void solve(int num) {
        int divisor = 0; //약수의 개수를 의미한다.
        for(int i=1;i<=num;++i){ //1~num까지 반복하여 num의 약수의 개수를 파악한다.
            if(num%i==0)
                ++divisor;
        }

        if(divisor==2) //1과 자기 자신만을 약수로 가지면 소수로 판단 count를 한다.
            ++count;
    }
}

 

---

 

2번

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

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

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

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

public class Main {
    static int count = 0; //입력 받은 수 중 전체적인 소수 개수

    //전체 시간 복잡도 : O(N(sqrt(N))
    //전체 공간 복잡도 : 자료구조 x
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //빠른 실행을 위해 버퍼를 이용해 입력을 받는다.
        br.readLine(); //여기에서는 N을 사용하지 않으니 br.readLine()만 하고 넘어가도 된다.

        StringTokenizer st = new StringTokenizer(br.readLine()); //" " 단위로 입력을 구분한다.

        //" "로 토크나이저의 문자열(토큰화한 문자열) 중에서 사용 가능한 토큰이 더 있는지 확인한다.
        //남아 있는 토큰이 있으면 true
        while(st.hasMoreTokens()){
            int num = Integer.parseInt(st.nextToken()); //다음 토큰을 num에 저장

            if(solve(num)) //소수 판별 함수 실행
                count++; //소수이면 count
        }

        System.out.println(count);
    }

    //시간 복잡도 : O(sqrt(N))
    //공간 복잡도 : 자료구조 x
    private static boolean solve(int num) {
        //아래 반복문에서 1,2를 포함하면 반복할 때마다 조건 처리를 따로 해줘야 하기 때문에 첫 실행에서 바로 검사해준다.
        if(num==1) //1은 소수가 아니다.
            return false;

        else if(num==2) //2는 소수다.
            return true;

        //주어진 수 num의 제곱근보다 큰 수는 검사할 필요가 없다.
        //왜?
        //일단 본질적으로 2를 제외한 '소수'는 2~Num-1까지 약수가 없어야한다.
        //여기에서 num의 제곱근보다 큰 수로 나눴을 경우
        //1> 나누어 떨어진다. => num의 제곱근보다 큰 수 순서가 오기 전에 num의 제곱근보다 작은 수에서 '소수가 아님' 이 판별이 난다.
        //2> 나누어 떨어지지 않는다. => Num의 약수가 아니다. => 굳이 계산할 필요가 없다.
        //따라서 위와 같은 결론을 도출할 수 있다.
        for(int i=2;i<=Math.sqrt(num);++i){
            if(num%i==0) //1과 자기자신을 제외한 약수가 있으면 '소수가 아님'을 판별
                return false;
        }

        return true;
    }
}