BackJoon Algorithm 2581 소수 (Java)

업데이트:
최대 1 분 소요

BackJoon Algorithm - Java

alt

문제

alt

  • 일반적으로 이중포문을 돌려 하나씩 다 대입해보면 시간초과가 나온다.
  • 에라토스테네스 체 알고리즘으로 소수를 구하는게 시간 복잡도가 가장 좋다.

풀이

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

public class Back_2581 {
    public static void main(String[] args) throws IOException {

        // given
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int M = Integer.parseInt(br.readLine());
        int N = Integer.parseInt(br.readLine());

        // N 배열 생성
        boolean prime[] = new boolean[N + 1];

        // 0하고 1은 소수가 아님
        prime[0] = true;
        prime[1] = true;

        // 에라토스테네스 체
        for (int i = 2; i <= Math.sqrt(prime.length); i++) {
            for (int j = i * i; j < prime.length; j += i) {
                prime[j] = true;
            }
        }
        int sum = 0;
        int small_count = 0;
        // when
        for (int i = M; i <= N; i++) {

            // i 가 소수이면
            if (prime[i] == false) {
                sum += i;

                // 첫 소수는 최소값
                if (small_count == 0) {
                    small_count = i;
                }
            }
        }

        // then
        if (sum == 0 && small_count == 0) {
            System.out.println(-1);
        } else {
            System.out.println(sum);
            System.out.println(small_count);
        }

        br.close();
    }
}


댓글남기기