백준 2581번 자바 문제 답/해설(소수 문제)

[1] 백준 카테고리

단계별로 풀어보기
기본 수학 2
2단계 2581번 문제
소수

[2] 문제

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.
예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

1. 입력
입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다.
M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다.

2. 출력

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 
단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

3. 예제 입력 1

60

100

4.예제 출력 1

620

61

 

3. 예제 입력 2

64

65

 

4.예제 출력 2

-1

[3] 정답
1. 정답 해설 미포함

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 NumberFormatException, IOException{
		
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		

		int A = Integer.parseInt(br.readLine());
		int B = Integer.parseInt(br.readLine());
		
		prime = new boolean[B+1];
		get_prime();
		
		
		int sum = 0;
		int min = Integer.MAX_VALUE;
		for(int i = A; i <=B; i++) {
			if(prime[i] == false) {
				sum += i;
				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++) {
			if(prime[i]) continue;
			for(int j = i * i; j < prime.length; j += i) {
				prime[j] = true;
			}
		}
		
	}
}

 

2. 정답 해설 포함

import java.io.BufferedReader;
/* BufferedReader 사용을 위해서 java.io.BufferedReader 클래스를 import 한다
Enter를 경계로 인식하고 받은 데이터는 String으로 고정된다.*/
import java.io.InputStreamReader;
/* byte 단위 데이터를 문자 단위 데이터로 처리할 수 있도록 변환해주기 위해서
InputStreamReader를 사용한다.
InputStreamReader 사용을 위해서 java.io.InputStreamRead 클래스를 import 한다. */
import java.io.IOException;
/* 예외처리를 위해서 IOException를 사용한다
IOException 사용을 위해서 java.io.IOException 클래스를 import 한다.*/

public class Main {
// 접근제어자 public으로 Main 클래스를 선언한다
	public static boolean prime[];
	// 접근제어자 public으로 메모리에 상주하게 boolean 형 배열 prime를 선언한다
	
	public static void main(String[] args) throws NumberFormatException, IOException{
	// 접근제어자 public으로 메모리에 상주하게 리턴값이 없이 main 함수를 선언한다
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// BufferedReader 객체 br를 선언한다

		int A = Integer.parseInt(br.readLine());
		// int형 변수 A를 선언하고 BufferedReader 객체 br를 사용해서 값을 입력받는다.
		int B = Integer.parseInt(br.readLine());
		// int형 변수 B를 선언하고 BufferedReader 객체 br를 사용해서 값을 입력받는다.

		prime = new boolean[B+1];
		get_prime();
		// 함수 get_prime를 사용한다.

		int sum = 0;
		// int 형 변수 sum를 선언하고 0으로 초기화한다.
		int min = Integer.MAX_VALUE;
		// int형 변수 min를 선언하고 정수의 최댓값 저장
		for(int i = A; i <=B; i++) {
		// A~B까지 for문 실행
			if(prime[i] == false) {
			// prime[i]가 false일 경우 괄호 안의 값 실행
				sum += i;
				// sum + i 값을 변수 sum에 저장
				if(min == Integer.MAX_VALUE) {
				// 변수 min에 정수의 최댓값 저장
					min = i;
					// 변수 min에 변수 i의 값을 저장
				}
			}
		}
		
		if(sum == 0) {
		// 변수 sum의 값이 0과 같을때 괄호안의 내용이 실행된다
			System.out.println(-1);
			// -1 출력
		}
		// 소수가 없으므로 -1를 출력한다
		else {
			System.out.println(sum);
			// 변수 sum에 저장된 값을 출력한다.
			System.out.println(min);
			// 변수 min에 저장된 값을 출력한다.
		}
		// 소수의 합과 소수의 최솟값을 출력한다
	}

	public static void get_prime() {
	// 접근제어자 public으로 메모리에 상주하게 리턴값이 없이 get_prime 함수를 선언한다
	
		prime[0] = true;
		// 변수 prime[0]에 true를 저장한다
		prime[1] = true;
		// 변수 prime[1]에 true를 저장한다
		// 0과 1은 소수가 아니므로 true를 저장한다

		for(int i = 2; i<= Math.sqrt(prime.length); i++) {
		// 2~prime.length의 제곱근까지 반복
			if(prime[i]) continue;
			// prime[i] 값이 true 일때 밑의 식이 실행된다
			for(int j = i * i; j < prime.length; j += i) {
			/* i*i~<prime.length 범위에서 반복
			에라토스테네스의 체로 소수를 걸려준다. */
				prime[j] = true;
				// true 값을 prime[j]에 저장
			}
		}
	}
}

 

			for(int j = i * i; j < prime.length; j += i) {
			/* i*i~<prime.length 범위에서 반복
			에라토스테네스의 체로 소수를 걸려준다. */

정수를 걸려주는 에라토스테네스의 체를 알고리즘화 해서 소수가 아닌 숫자를 제거한다.