[Java] 백준 풀기 2581 - 소수

자바 백준 2581번

브론즈 2

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

2581번: 소수

 

 

 

 

 

문제 보기

분류: 수학, 정수론, 소수 판정

 

 

 

 

 

문제 풀기

주어진 구간의 숫자들을 하나씩 소수인지 판별한다.

 

소수 판별은 2부터 제곱근 N까지 구간에서 for loop을 이용하여 나누어 떨어지는 경우가 있으면 false를 반환하고 그렇지 않으면 true를 반환하여 판단한다.

 

for loop으로 구간의 작은수부터 확인할때 소수가 나오면 첫 소수를 minPrime에 저장한다.

구간의 소수에 대해 누적합을 한다.

 

minPrime이 초기값 -1을 유지하고 있으면 소수가 없는것으로 결과 출력하고, 그렇지 않으면 모든 소수의 합과 최속값을 출력한다.

 

 

 

 

 

코드 보기

import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // M, N 입력
        int M = sc.nextInt();
        int N = sc.nextInt();
        
        // 찾아야 할 소수의 합, 최소값
        int sum = 0;
        int minPrime = -1;
        
        // M부터 N까지 구간의 숫자를 하나씩 확인
        for (int num = M; num <= N; num++) {
            // 소수 true or false
            if (isPrime(num)) {
                sum += num;  // 소수 누적합
                if (minPrime == -1) {  // 첫 소수가 발생했을때
                    minPrime = num;  // 최소값에 저장
                }
            }
        }
        
        // 소수 유무에 따른 조건 분기
        if (minPrime == -1) {  // 소수가 발견되지 않아 초기값
            System.out.println("-1");
        } else {  // 소수가 하나 이상 나타났을때
            System.out.println(sum);
            System.out.println(minPrime);
        }
    }

    private static boolean isPrime(int num) {
        // 1 이하는 소수 아님
        if (num < 2) {
            return false;
        }
        // 약수가 존재하는지 판별
        for (int i = 2; i <= Math.sqrt(num); i++) {  // 빠른 소수 판단을 위해 제곱근까지 확인
            if (num % i == 0) {
                return false;  // 1 또는 N이 아닌 약수가 존재
            }
        }
        return true;  // 1 또는 N이 아닌 약수 없음
    }
    
}