[백준] - 소수 (2581) (자바/Java)

 

 

 

 

 

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

 

 

 

 

 

 

 

 

 

 

 

문제.

---

 

 

 

 

 

 

 

 

풀이.

---

 

import java.util.Scanner;

public class Main {
    public static boolean[] prime;
    public static void main(String[] args){

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

        prime = new boolean[n + 1]; //배열 생성
        make_prime(n);

		//소수 합, 최소값
        int sum = 0;
        int min = Integer.MAX_VALUE;
        for (int i = m; i <= n; i++) {
            if (prime[i] == false) { //false = 소수
                sum += i;
                if (min == Integer.MAX_VALUE) { //최소값
                    min = i;
                }
            }
        }

        if (sum == 0) {
            System.out.println(-1);
        }else {
            System.out.println(sum);
            System.out.println(min);
        }

    }

	// 에라토스테네스 체 알고리즘
    public static void make_prime(int num) {

        prime[0] = true;
        prime[1] = true;

        for (int i = 2; i < Math.sqrt(num); i++) {
            for (int j = i * i; j < prime.length; j = j + i) {
                prime[j] = true;
            }
        }

    }

}

 

이번문제는 " 소수 " 문제이다.

풀면서 느낀 점은 생각보다 어려웠다....?? 지난번 소수 구하기 문제는 괜찮게 풀었었는데 몇 가지만 추가되었다고 

난이도가 오른 느낌이였다... 그래서 구글링을 통해서 검색도 해보고 해서 풀었던 문제다...

하지만 풀이 설명하기에 아직 부족함이 많아 밑에 참고한 블로그 링크를 남겨두도록 하겠다...

 

<에라토스테네스 체 알고리즘>

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

JAVA [자바] - 소수 구하는 알고리즘 및 구현