[Java][BaekJoon][2581] 소수

<문제의도>

여러가지 소수 판별법을 적절히 사용해서 문제를 해결할 수 있느냐 묻는 문제이다

 

<풀이코드>

import java.util.ArrayList;

import java.util.Scanner;

public class BaekJoon_Java_2581 {

    public static void main(String[] args) {

        Scanner scn = new Scanner(System.in);

        int M = scn.nextInt();

        int N = scn.nextInt();

        ArrayList<Integer> PrimeList = new ArrayList<>();

        // int PrimeArray[] = new int[(N-M)+1]; //+1 해주는 이유는 경계값 포함하기 때문

        int count = 0;

        for ( int i = M ; i <= N ; i++){

            int tempCount = 0 ;

            for ( int k = 1 ; k <= i ; k++){

                if( i % k == 0){

                    tempCount++;

                    if(tempCount > 2){

                        break;

                    }

                }

            }

            if ( tempCount == 2){

                PrimeList.add(i);

            }

        }

        int sum = 0;

        // int min = M;

        for (int e : PrimeList){

            sum += e;

        }

        if( sum == 0){

            System.out.println("-1");

        }else{

            System.out.println(sum);

            System.out.println(PrimeList.get(0));

        }

    }

}

<풀이과정>

같은 소수판별법을 사용했고, 이번엔 ArrayList함수를 한번 사용해 보았다.

int 배열로 만드는건 여러번 해봤기 때문에 다른걸로 한번 만들어 보았다. 아무래도 api다 보니 사용이 편하고

깔끔하게 정리가 가능했다.

추가로 다른 풀이 법을 찾아봤는데 소수 판별법은 에라토스테네스의 체라는 것을 시간복잡도 때문에 대부분 사용하는것 같다.  그래서 추가로 코드를 아래다 정리해 놓았따.

import java.util.Scanner;

 

public class Test {

 

    public static boolean[] prime;  // 소수를 체크할 배열

    public static void main(String[] args) {

 

        Scanner in = new Scanner(System.in);

       

        int N = in.nextInt();

       

        make_prime(N);

 

        for(int i = 0; i < prime.length; i++) {

            if(prime[i] == false) { // 소수(false)일 경우 출력

                System.out.println(i);

            }

        }

    }

 

    // N 이하 소수 생성 메소드

    public static void make_prime(int N) {

       

        prime = new boolean[N + 1]; // 0 ~ N

 

        /*

        소수가 아닌 index = true

        소수인 index = false

        */

       

        // 2 미만의 N 을 입력받으면 소수는 판별할 필요 없으므로 바로 return

        if(N < 2) {

            return;

        }

       

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

       

       

        // 제곱근 함수 : Math.sqrt()

        for(int i = 2; i <= Math.sqrt(N); i++) {

       

            // 이미 체크된 배열이면 다음 반복문으로 skip

            if(prime[i] == true) {

                continue;

            }

       

            // i 의 배수들을 걸러주기 위한 반복문

            for(int j = i * i; j < prime.length; j = j+i) {

                prime[j] = true;

            }

        }

 

    }

 

}

<문제 출처>

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

2581번: 소수