[백준알고리즘/기본 수학 2단계] 2581번 문제 : 소수

안녕하세요

백준 알고리즘 단계별로 풀어보기 8단계 2581번 문제 소수를 풀어봤습니다

이전 문제 1987번의 소수 찾기의 업그레이드 버전입니다

소수 찾기를 풀었다면 어렵지 않게 풀 수 있는 문제입니다!

제가 푼 방법들에 대해서 알아보겠습니다

 

---

문제 링크입니다

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

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을 출력한다.

 

 

---

 

 

문제 풀이

첫 번째 방법

기본적인 소수 판별 방법으로 풀은 방식입니다

2부터 하나씩 더해서 소수인지 판별하려는 수와 나누었을 때 나누어 떨어지면 소수가 아니게 됩니다

그렇게 시작값부터 종료값 사이의 소수를 구해 정답을 도출합니다

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

public class Main {
	public static void main(String[] args) throws IOException {
		// BufferedReader 변수 및 StringTokenizer 변수 선언 및 데이터 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int A = Integer.parseInt(br.readLine());
		int B = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		int sum = 0; // sum변수
		int Min = -1; // Min변수
		
		// A부터 B사이의 합계와 최솟값을 구한다
		for(int i = A; i <= B; i++)
		{
			if(isPrime(i)) {
				sum += i;
				
				if(Min == -1)
					Min = i;
			}
		}
		
		// Min이 -1이면 소수가 없다
		if(Min == -1)
			sb.append(-1);
		else 
			sb.append(sum).append("\n").append(Min);
		
		// 결과 출력
		System.out.print(sb);
	}
	
	static boolean isPrime(int Number) // 소수 판별 메서드 선언
	{
		if(Number == 1) // 1은 소수x
			return false;
				
		for(int i = 2; i < Number; i++) // 2부터 나누어떨어지면 소수x
			if(Number % i == 0) return false;
		
		return true;
	}
}

 

---

두 번째 방법

두 번째 방법은 에라토스테네스의 체를 사용한 방법입니다

소수의 배수들을 전부 지워나가는 방식으로 소수를 구하는 방법입니다

에라토스테네스의 체를 사용해 소수를 기록한 배열을 만든 후 비교하여 소수인지 아닌지 판별해줍니다

첫 번째와 동일한 방법으로 시작값 A, 마지막값 B를 입력받아 합계와 최솟값을 구해줍니다

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

public class Main {
	public static void main(String[] args) throws IOException {
		// BufferedReader 변수 및 StringTokenizer 변수 선언 및 데이터 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int A = Integer.parseInt(br.readLine());
		int B = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		int sum = 0; // sum변수
		int Min = -1; // Min변수
		
		boolean[] Prime = new boolean[10001]; // 소수판별 배열 선언		
		Prime[0] = true;
		Prime[1] = true;
		
		// 에라토스테네스의 체 -> 제곱근까지만 반복한다 -> Prime배열이 true이면 소수x
		for(int i = 2; i <= Math.sqrt(10000); i++) {
			if(Prime[i] == true)
				continue;
			
			for(int j = i * i; j < 10001; j = j + i)
				Prime[j] = true;
		}

		// A부터 B사이의 합계와 최솟값을 구한다
		for(int i = A; i <= B; i++)
		{
			if(Prime[i] == false) {
				sum += i;

				if(Min == -1)
					Min = i;
			}
		}

		// Min이 -1이면 소수가 없다
		if(Min == -1)
			sb.append(-1);
		else 
			sb.append(sum).append("\n").append(Min);

		// 결과 출력
		System.out.print(sb);
	}
}

 

여기까지 제가 푼 두 가지 방법에 대해서 알아봤습니다

---

속도 비교

1. 메서드 사용 방법

2. 에라스토테네스의 체 사용 방법

역시 메모리 및 시간이 2번 방법이 훨씬 더 빠르네요 ㅎ

 

참고로 에라스토테네스의 체를 사용한 방법은 JAVA11로 제출한 방식 중에서 1등이 나왔네요 뿌듯! ㅎㅎ

 

이상 백준 알고리즘 2581번 소수를 풀은 내용이었습니다!

 

이전 문제 : 2021.05.28 - [알고리즘/알고리즘JAVA] - [백준알고리즘/기본 수학 2단계] 1978번 문제 : 소수 찾기

다음 문제 :