[BaekJoon] 2581번 소수 문제풀이 (Success)

2581번: 소수

 

☕Language: Java

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int min = Integer.parseInt(br.readLine());
        int max = Integer.parseInt(br.readLine());
 
        if(min==1) {
            calPrimeNum(min+1, max);
        } else {
            calPrimeNum(min, max);    
        }
        
    }
 
    public static void calPrimeNum(int min, int max) throws IOException {
 
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        boolean[] bArr = new boolean[10001];
 
        for (int i = min; i <= max; i++) {
            for (int j = 2; j < i; j++) {
                if (i % j == 0) {
                    bArr[i] = true;
                    break;
                }
            }
        }
 
        int last = 0;
        int sum = 0;
 
        while (max >= min) {
            if (!bArr[max]) {
                sum += max;
                last = max;
            }
 
            max--;
        }
 
        if (last == 0) {
            bw.write(-1 + "");
        } else {
            bw.write(sum + "\n" + last);
        }
 
        bw.flush();
        bw.close();
    }
 
}
 

🤔 해설

1. main() - if 조건문

    - 1인 소수가 아니므로 min==1인 경우에는 calPrimeNum()에서 따로 조건문 처리를 해야하지만, 복잡해지는 걸 방지하기 위해 main()에서 먼저 처리

2. calPrimeNum()

    - for 반복문

        - min ~ max 까지 2이상의 수로 나누어 떨어질 경우, boolean 값 false(Default) → true로 변환

        - 소수가 아닐 경우, break를 활용하여 시간 단축

    - while 반복문

        - 최소값을 구하기 위해 max부터 last 변수에 대입

    - if 조건문

        - last == 0 일 경우, 소수가 없는 것이므로 -1 출력

 

 

😮 이 외의 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int min = Integer.parseInt(br.readLine());
        int max = Integer.parseInt(br.readLine());
 
        if(min==1) {
            calPrimeNum(min+1, max);
        } else {
            calPrimeNum(min, max);    
        }
        
    }
 
    public static void calPrimeNum(int min, int max) throws IOException {
 
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        boolean[] bArr = new boolean[10001];
 
        for (int i = min; i <= max; i++) {
            for (int j = 2; j <= Math.sqrt(i); j++) {
                if (i % j == 0) {
                    bArr[i] = true;
                    break;
                }
            }
        }
 
        int last = 0;
        int sum = 0;
 
        while (max >= min) {
            if (!bArr[max]) {
                sum += max;
                last = max;
            }
 
            max--;
        }
 
        if (last == 0) {
            bw.write(-1 + "");
        } else {
            bw.write(sum + "\n" + last);
        }
 
        bw.flush();
        bw.close();
    }
 
}

- 로직은 그대로지만, 소수 판별 범위를 제곱근까지로 축소

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
 
public class Main {
 
    public static boolean[] bArr;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int min = Integer.parseInt(br.readLine());
        int max = Integer.parseInt(br.readLine());
 
        calPrimeNum(min, max);
 
        int sum = 0;
        int first = 0;
        for (int i = max; i >= min; i--) {
            if (!bArr[i]) {
                sum += i;
                first = i;
            }
        }
 
        if (first != 0) {
            bw.write(sum + "\n" + first);
        } else {
            bw.write("-1");
        }
 
        bw.flush();
        bw.close();
 
    }
 
    public static void calPrimeNum(int min, int max) throws IOException {
        bArr = new boolean[max + 1];
 
        bArr[0] = true;
        bArr[1] = true;
 
        for (int i = 2; i < Math.sqrt(max); i++) {
            if (bArr[i]) {
                continue;
            }
 
            for (int j = i * i; j < bArr.length; j += i) {
                bArr[j] = true;
            }
        }
 
    }
 
}

- calPrimeNum()

1. bArr

    - 소수 판별 배열을 전역으로 설정하여, 2개의 메서드에서 공유

    - 0, 1을 true로 변경하여 소수로 처리되지 않도록 함

2. for 반복문

    - j를 i * i부터 시작하는 이유

        - i가 소수가 아닐 경우, 이전 for문에서 이미 처리 처리되어 if 조건문에 의해 다음 숫자로 넘어감

        - i가 소수일 경우, bArr값이 false로 유지

        - i * 2 = 2의 배수, i * 3 = 3의 배수, ... , i * (i-1) = (i-1)의 배수

    - j에 i를 더해서 배수를 계산

 

 

 

🔗 소스 코드
HJ0216/TIL/BOJ

 

📚 참고 자료

[백준] 2581번 : 소수 - JAVA [자바]