[백준] 2581번 : 소수 - Java

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

2581번: 소수

---

---

참고 유형

https://unknownomad.tistory.com/147

[백준] 1978번 : 소수 찾기 - Java

---

알고리즘

에라토스테네스의 체

• 소수 판별법 중 가장 대표적인 방법 중 하나
• 여러 개의 소수를 체를 거르듯 구하기
• 2를 제외한 2의 배수 모두 거르기 ... 3을 제외한 3의 배수 모두 거르기 ... (반복)
• 이 또한 2번 방법처럼 구하려는 범위의 최대값의 제곱근까지만 반복하면 됨

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_complexity

---

풀이

1. Scanner

import java.util.Scanner;
 
public class Main {
    public static boolean prime[];
    
    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(); //에라토스테네스의 체 메서드
		
        //해당 범위 내 소수들의 합 & 최소값 
        int sum = 0;
        int min = Integer.MAX_VALUE;
        for(int i = M; i <= N; i++) {
            if(prime[i] == false) { //false = 소수
                sum += i;
                
                //첫 소수값 담으면 학. 조건으로 인해 이후 min 값 고정됨
                //Integer.MAX_VALUE = 2147483647
                if(min == Integer.MAX_VALUE) {
                    min = i;
                }
            }
        }
		
        if(sum == 0) { //소수가 없다면
            System.out.println(-1);
        } else {
            System.out.println(sum);
            System.out.println(min);
        }
	}
	
    // 에라토스테네스의 체 알고리즘 
    public static void get_prime() {
        prime[0] = true;
        prime[1] = true;
		
        for(int i = 2; i <= Math.sqrt(prime.length); i++) {
            for(int j = i * i; j < prime.length; j += i) {
                prime[j] = true;
            }
        }
    }
}

 

2. BufferedReader

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
 
public class Main {
    public static boolean prime[];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int M = Integer.parseInt(br.readLine());
        int N = Integer.parseInt(br.readLine());
		
        prime = new boolean[N + 1]; //배열 생성
        get_prime(); //에라토스테네스의 체 메서드
		
        //해당 범위 내 소수들의 합 & 최소값 
        int sum = 0;
        int min = Integer.MAX_VALUE;
        for(int i = M; i <= N; i++) {
            if(prime[i] == false) { //false = 소수
                sum += i;
                
                //첫 소수값 담으면 학. 조건으로 인해 이후 min 값 고정됨
                //Integer.MAX_VALUE = 2147483647
                if(min == Integer.MAX_VALUE) {
                    min = i;
                }
            }
        }
		
        if(sum == 0) { //소수가 없다면
            System.out.println(-1);
        } else {
            System.out.println(sum);
            System.out.println(min);
        }
	}
	
    // 에라토스테네스의 체 알고리즘 
    public static void get_prime() {
        prime[0] = true;
        prime[1] = true;
		
        for(int i = 2; i <= Math.sqrt(prime.length); i++) {
            for(int j = i * i; j < prime.length; j += i) {
                prime[j] = true;
            }
        }
    }
}

---

성능

• BufferedReader > Scanner

 

---

출처 : https://st-lab.tistory.com/83