Algorithm/Baekjoon(Java)

[백준/JAVA] 2581 : 소수 찾기 ( 기본 수학 2 )

비망노트 2022. 8. 8. 22:38
문제

자연수 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

 

⭕ 풀이

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int m = Integer.parseInt(br.readLine());
        int n = Integer.parseInt(br.readLine());
        br.close();
        
        int sum = 0, minSosu = 0, count =0;
        while(m<=n){
            count = 0;
            for(int i=1;i<=m;i++){
                if(m%i==0){
                    count++;
                    if(count>2){break;}
                }
            }
            if(count==2){
                if(minSosu==0){minSosu=m;}
                sum+=m;
            }
            m++;
        }
        System.out.println(minSosu==0?-1:sum+"\n"+minSosu);
    }
}

✅ 이전문제였던 소수찾기에서 소수를 누적합할 sum변수와 가장작은 값을 갖고있을 변수를 만들어 풀이했는데

아무래도 기본수학인데 주먹구구식으로 푸는것같아 다른분들의 풀이를 찾아보았다.

 

 

✅ 다른분의 풀이

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

/*
https://www.acmicpc.net/problem/2581
 */
public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int start = Integer.parseInt(br.readLine());
        int num = Integer.parseInt(br.readLine());
        int min = num;
        int sum = 0;

        boolean[] isPrime = new boolean[num + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;

        for (int i = 2; i * i <= num; i++) {
            if (isPrime[i]) { // i가 소수이면,
                // i의 배수는 소수가 아님.
                for (int j = i * i; j <= num; j += i) {
                // i가 5인 경우. 2 * 5, 3 * 5, 4 * 5는 이미 2와 3에서 false로
                // 처리되었음.
                    isPrime[j] = false;
                }
            }
        }

        for (int i = start; i <= num; i++) {
            if (isPrime[i]) {
                if (i < min) {
                    min = i;
                }
                sum += i;
            }
        }
        if (sum > 0) {
            System.out.println(sum);
            System.out.println(min);
        } else {
            System.out.println(-1);
        }
    }
}

✅

i가 2일때 isPrime[i] i가 true라면
j는 4 6 8 10 .... num보다 작거나 같을때까지 2의배수를 다 false로 만든다

i는 3이되었고 
이전반복문에서 3이 false로 바뀐적은 없기때문에
j는 6을 시작으로 3의배수를 모두 false로 만든다

i는 4가되었지만 이전 2일때의 반복에서 4는 false가 되었으므로 내부for문 실행하지않음

i는 5가되었고 true이므로
j는 10부터시작해 5의배수를 모두 false로만듦

 

이렇게 쭉 반복하여 주어진 num길이만큼의 생성한 boolean배열에서

소수는 true인 상태로두고 소수가아닌경우 false로 모두 초기화가 완료된상태이다

 

이제 첫줄에 입력된 수를 i 로 받아서 1씩 증가시키며

boolean배열의 해당 인덱스가 true라면 해당소수를 min으로 받아둔뒤

if문을 나와서 sum에 누적한다.

 

 

✅ 소수 개념돕기

https://st-lab.tistory.com/81

 

 

-출처

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