[백준 알고리즘 문제풀이][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은 10,000이하의 자연수이며, M은 N보다 작거나 같다.

출력

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.
단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

시간제한

1초

알고리즘 유형

수학
정수론
소수 판정

예제입력 1

60
100
  

예제출력 1

    620
61
  

예제입력 2

64
65
  

예제출력 2

-1

풀이 1

import java.util.Scanner;

public class No2581_소수 {

  public static void main(String[] args) {
    go();
  }

  private static void go(){

    Scanner sc = new Scanner(System.in);
    int m = sc.nextInt();
    int n = sc.nextInt();

    boolean[] arr = new boolean[n+1];   //0번도 포함해야 되니까 0+1
    for(int x=2; x<arr.length; x++) arr[x] = true;  //기본값 true 처리(소수) / 인덱스 0, 1은 소수아니므로 소수처리 안해줌

    //arr내에서 소수아닌 아이들 걸러내기
    for(int x=2; x<=n; x++){
      if(arr[x]){ //첫번째 아이는 소수 맞음
        for(int y=2; y<=n/x; y++){  //소소의 배수들에 대해 소수아님 처리
          arr[x*y] = false;
        }
      }
    }
    int min=-1;
    int sum=0;
    for(int x=m; x<=n; x++){
      if(arr[x]){
        if(min==-1) min = x;
        sum+=x;
      }
    }
    if(sum>0)System.out.println(sum);    //범위내 소수합
    System.out.println(min);    //범위내 소수중 최소값

  }


}

GitHub 소스는 아래에서 확인 가능합니다.

[풀이1]

Baekjoon Algorithm solve JAVA No.2581 소수

이전[백준 알고리즘 문제풀이][JAVA][2577번] 숫자의 개수

다음[백준 알고리즘 문제풀이][JAVA][2675번] 문자열 반복