[코드트리] 범위 내의 소수 1 - 자바(Java)

문제

https://www.codetree.ai/problems/prime-range-1?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

숫자 두 개가 주어집니다. 이 두 수 사이의(경계 포함) 소수의 합과, 가장 작은 소수를 출력하는 프로그램을 작성해 보세요. 만약 사이에 소수가 한 개도 없다면 둘 다 0을 출력하세요.

 

입력 예시 1

1 3

 

출력 예시 1

5 2

 

입력 예시 2

123 456

 

출력 예시 2

16139 127

 

 

코드

첫 번째 줄에 숫자 두 개가 공백을 사이에 두고 주어집니다. 앞의 숫자가 뒤의 숫자보다 작거나 같게 주어집니다.

• 1 ≤ 주어지는 숫자 ≤ 1,000,000

 

주어진 두 수 사이의 소수의 합과, 가장 작은 소수를 출력하세요.

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken()); // 앞의 숫자
        int b = Integer.parseInt(st.nextToken()); // 뒤의 숫자

        long sum = 0; // 소수의 합
        int min = 0; // 가장 작은 소수

        // 가장 작은 소수 구하기
        for (int i = a; i <= b; i++) {
            if (isPrime(i)) {
                min = i;
                break;
            }
        }

        // 소수들의 합 구하기
        for (int i = a; i <= b; i++) {
            if (isPrime(i)) {
                sum += i;
            }
        }

        bw.write(sum + " " + min);
        bw.flush();
        bw.close();
    }

    // 소수 판별하기
    private static boolean isPrime(int num) {
        if (num < 2) { // 2보다 작으면 소수 아님
            return false;
        }

        // 2의 제곱근만큼 반복
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) { // num이 i로 나누어 떨어지면
                return false; // 소수 아님
            }
        }

        return true;
    }
}