[Java] 백준 #2581 (기본 수학2)

📍 출처

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

📝 문제

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.

예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

⌨️ 입력

입력의 첫째 줄에 M이, 둘째 줄에 N이 주어진다.

M과 N은 10,000이하의 자연수이며, M은 N보다 작거나 같다.

🖨 출력

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

단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

⌨️ 예제 입력 1

60
100

🖨 예제 출력 1

620
61

⌨️ 예제 입력 2

64
65

🖨 예제 출력 2

-1

📚 내가 제출한 코드

• 보편적인 알고리즘

import java.util.Scanner;

public class App {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);

		int num1 = sc.nextInt();
		int num2 = sc.nextInt();
		int sum = 0; //합
		int min = Integer.MAX_VALUE; //최솟값

		for(int i = num1 ; i <= num2 ; i++){
				//소수이면 실행
				if(check(i)){
					sum += i;
				if(min == Integer.MAX_VALUE){ //아직 min이 변하지 않았으면 실행
					min = i;
				}
			}
		}
		if(sum == 0){
			sum = -1;
			System.out.println(sum);
		}else{
			System.out.println(sum);
			System.out.println(min);
		}
	}

	private static boolean check(int i){
		//소수이면 true, 아니면 false
		if(i == 1){return false;}

		for(int j = 2; j <= Math.sqrt(i); j++){
			if(i % j == 0){return false;}
		}

		return true;
	}
}

• 에라토스테네스의 체

import java.util.Scanner;

public class App {
	static boolean prime[];

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);

		int num1 = sc.nextInt();
		int num2 = sc.nextInt();
		prime = new boolean[num2 + 1];

		get_prime();

		int sum = 0; //합
		int min = Integer.MAX_VALUE; //최솟값

		for(int i = num1 ; i <= num2 ; i++){
				if(prime[i] == false){
					sum += i;
					if(min == Integer.MAX_VALUE){min = i;}
				}
		}


		if(sum == 0){
			sum = -1;
			System.out.println(sum);
		}else{
			System.out.println(sum);
			System.out.println(min);
		}
	}

	private static void get_prime(){
		//소수이면 false, 아니면 true
		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;
			}
		}
	}
}

✏️ 내가 제출한 코드에 대한 설명

문제를 에라토스테네스의 체와 일반 알고리즘 두 가지로 풀어보았다.

첫 번째의 경우 에라토스테네스의 체를 사용하지 않은 것으로 check 메소드를 만들어 check 안에서 소수이면 true 아니면 false를 반환하여 소수의 경우 sum에 더하여주는 식으로 해결하였다. 또한 최솟값은 처음 받은 소수인데 min이라는 int형 변수에 Integer.MAX_VALUE를 사용하여 int형에서 사용할 수 있는 가장 큰 수를 저장해둔다. 그 이유는 가장 작은 소수를 반환 받을 때 Integer.MAX_VALUE보단 작을 것이기 때문이다. 만약 min이 Integer.MAX_VALUE일 경우 아직 첫 번째 소수로 초기화하지 않은 것으로 조건을 설정하여 해결하였다.

두번째 코드는 에라토스테네스의 체를 사용한 것으로 에라토스테네스 체란 소수를 구할 때 모든 합성수를 구하고 합성수가 아닌 것이 소수다 라는 알고리즘이다. 따라서 합성수에는 true를 넣었으며 true가 아닐경우 소수인 것을 사용하여 문제를 해결하였다.