[백준알고리즘-JAVA]2581번 풀이(소수) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 2581번 풀이입니다. 


* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 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이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그중 최솟값을 출력한다. 

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

입력 예시

60
100

출력 예시

620
61

입력 예시

64
65

출력 예시

-1

성공코드

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

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());

	   		int s = 0;
	   		int n = 0;
	   		int sum = 0;
	   		int min_value = 0;
	   		
	   		for(int i = min ; i <= max ; i++) {
	   			if(i !=1) {
	   				for(int j = 2 ; j <= (int)Math.sqrt(i) ; j ++) {
	   				if(i%j == 0) {
	   					s += 1;
	   					//break;
	   				}
	   				}
	   				if(s == 0 ) {
	   					//System.out.println(i);
	   					sum += i;
	   					n += 1;
	   					if(n == 1) min_value = i;
	   				}
	   				s = 0 ;
	   			}
	   		}
	   		System.out.println(sum !=0 ? sum + "\n" + min_value : -1);
		}
		}

 

해당 알고리즘은 이전에 풀어보았던 백준 1978(소수 찾기)을 참고하여 쉽게 만들어 볼 수 있었습니다.

[백준알고리즘-JAVA]1978번 풀이(소수 찾기) - 초보도 이해하는 풀이

해당 글에서 소수 찾기를 이해하셨다면, 보다 쉽게 이번 알고리즘을 푸실 수 있었을 겁니다!!

 

알고리즘 흐름도를 생각하면서 각 STEP을 따라오시면, 어느순간 알고리즘이 이해되어있는 자신을 발견할 수 있습니다!

 

---

소수 알고리즘의 흐름도

 

입력받기 -> 받음입력 중 작은 입력에서 큰 입력으로 반복문을 돌려 하나씩 소수를 판별한다. -> 소수가 맞다면 그 합계 뜰을 더해간다. 단, 처음 소수를 count 할 때의 값을 저장해준다. -> 반복문을 끝낸 후 합계와 처음 소수 값을 출력한다.

---

STEP1 작은값 큰 값으로 for문 돌리기

int min = Integer.parseInt(br.readLine());
int max = Integer.parseInt(br.readLine());
for(int i = min ; i <= max ; i++) {
}

입력받은 두입력을 각각 min, max변수에 담아 그 사이 값으로 for문을 돌려줍니다.

 

이번 STEP에서는 입력 예시 60 100을 기준으로 해결해나가 보겠습니다.

 

그렇게 되면 STEP1의 코드는 60에서부터 100까지 반복을 하겠죠 ~?

 

---

STEP2 소수 판별하기-1

소수 찾기에 대한 자세한 내용은 앞선  백준 1978번 소수 글을 참고하시면 됩니다.!

 

여기서는 간단히 설명해드리겠습니다. 60이 소수인지 판별하기 위해서는 2부터 루트(60)까지의 숫자들을 증가해가면서 하나씩 나누어서 나누어진다면 60의 소인수가 존재한다는 의미가 됩니다.

 

즉, 나누어진다면, 60은 소수가 되지 않는다는 말이죠. 이런 식으로 또 하나의 반복문을 돌리는 과정이 필요합니다.

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

	   				}

---

STEP 3 소수 판별하기-2

이제 몇가지 제약사항을 고려하셔야 합니다.

 

일단 첫번째, 앞서 소수 판별하기 - 1에서 판별해낸 소수들을 더할 sum이 필요합니다.

for(int j = 2 ; j <= (int)Math.sqrt(i) ; j ++) {
	   				if(i%j == 0) {
	   					s += 1;
	   				}
	   				}
	   				if(s == 0 ) {
	   					sum += i;
	   				}

여기서 s는 60의 소수가 몇 개인지를 알려주는 것이겠죠? 저 s가 1개 이상, 즉 양수라면 소수가 아니게 되죠. 그렇지 않고 만약 초기에 설정해준 0이 그대로 나온다면, 소수라는 의미겠죠? 60은 소수가 아니니 한 번 더 돌아 61이라고 가정하죠

 

sum에는 61의 숫자가 들어가게 되겠죠.

 

두 번째, 소수 최소값찾기

for(int j = 2 ; j <= (int)Math.sqrt(i) ; j ++) {
	   				if(i%j == 0) {
	   					s += 1;
	   				}
	   				}
	   				if(s == 0 ) {
	   					sum += i;
                        n += 1;
	   					if(n == 1) min_value = i;
	   				}

간단합니다. 그냥 아무 변수나 선언해준 뒤, 소수가 판별되면 +1을 해주는 겁니다. 그리고 그 변수가 1이라면 바로 최소의 소수가 되겠죠? 그 값을 출력해 주시면 됩니다.

 

세 번째 아까 소수를 판별할 때 2부터 시작했으니 1이 들어오는 경우를 예외처리를 해주어야 합니다.

if(i !=1) {
	   				for(int j = 2 ; j <= (int)Math.sqrt(i) ; j ++) {
	   				if(i%j == 0) {
	   					s += 1;
	   				}
	   				}
	   				if(s == 0 ) {
	   					sum += i;
	   					n += 1;
	   					if(n == 1) min_value = i;
	   				}
	   				s = 0 ;
	   			}
	   		}

if문 만약 1이라면 소수가 아니죠? 그냥 한 번 더 포문을 돌아가게 앞서 작성한 코드들을 if문으로 묶어주면 끝!

 

여기서 s=0;의 경우 소수를 못 찾았을 경우 s는 양수가 됩니다. 이를 다시 한번 초기화해서 다음 숫자들을 판별할 수 있게 해주어야 합니다!!

 

---

이런 식으로 해당 알고리즘을 풀어볼 수 있습니다.

System.out.println(sum !=0 ? sum + "\n" + min_value : -1);

참고로 출력 코드는 sum이 0 이 아니라면 sum과 min_value를 출력하고 0이라면 -1을 출력하라는 말입니다. 즉 sum이 0 이면 소수인 수가 하나도 없다는 의미가 되니깐요 ~