[백준 알고리즘, 소수] 알고리즘 문제 :: 2581번 소수

오늘은 단계별로 문제풀기

소수 두 번째 문제를 풀어봤어요

저번 문제 때 쓴 코드를 약간만 변형하면 풀 수 있어요

 

백준 알고리즘

 

바로 전 단계 문제가

1978번 문제인데여

코드는 아래에서 보실 수 있어요

https://hoho325.tistory.com/21

[백준 알고리즘, 소수] 알고리즘문제, 1978번: 소수찾기

 

문제

---

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

 

예를들어 60이랑 100이 입력되면 620과 61이 두 줄에 이어서 출력이 되어야되요

만약 64랑 65가 입력되면 두 수 사이에 소수가 없으니까 -1이 출력이 되어야되요

 

백준 알고리즘 2581번 소수

자바 소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Exam {

	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int [] arr = new int[2];	// 입력 받은 숫자 저장
		
		// 두 숫자 입력받기
		for(int i=0; i<2; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int count = 0;
		int prime_count = 0;	// 소수의 개수
		int sum=0;
		
		int number = arr[0];
		int min = 0;
		
		for(int i=0; i<=(arr[1] - arr[0]); i++) {
			for(int j=2; j<=number; j++) {
				if (number % j == 0) {
					count += 1;
				}
			}
			if ( count == 1) {
				prime_count++;
				sum += number;	// 소수들의 합
				if (prime_count == 1)
					min = number;	// 처음 소수로 판별된 수가 최솟값
			}
			count =0;
			number++;	// 소수를 판별할 수를 증가
		}
		
		// 소수가 없을 경우
		if (prime_count ==0) {
			bw.write("-1");
		}
		else {
			bw.write(Integer.toString(sum) + "\n");
			bw.write(Integer.toString(min) + "\n");
		}
			
		br.close();
		bw.close();
	}

}

전에 했던 소수를 구하는 프로그램에서 조금 변형을 시켰어요

첫 번째로 입력한 숫자에서 부터 1씩 증가시키면서

두번째로 입력받은 숫자 전까지 소수인지 아닌지 검사를 했어요

 

그렇게 해서 소수의 개수가 0개이면

소수가 없는걸로 판단해서 -1출력

소수의 합은 소수로 판별 될때마다 더하고

최솟값은 소수를 판별하는 중에 처음 나온 소수가 최솟값이니까

소수 count가 1로 될때 최솟값을 저장해서 출력!!

 

이렇게 하니까 금방 해결했네요

근데 첫번째 제출에 실패...

그 이유는 두번째로 입력한 수를 포함안시켰어요...

2랑 3입력하면 둘다 소수로 해야하는데 3미만 으로해서.. ㅠㅠㅠ

앞으로 더욱 꼼꼼하게 문제읽기!!