[백준] 1929번-소수 구하기-Java

12 Jun 2023 in Algorithm on Algorithm

[백준] 1929번-소수 구하기-Java

---

❓문제

1. 정수 M과 N을 입력받아 M~N사이의 소수를 모두 출력하라.
   

M,N의 범위

1 ≤ M ≤ N ≤ 1,000,000

🖊️풀이법

1. 입력 M과 N을 입력받아 필드에 선언한다.
2. a가 소수인지 판별하는 메서드를 정의한다.
3. N-M+1 번의 반복문을 반복하며 a가 소수인 경우, 출력한다.

정답 코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        for(int i = M; i <= N; i++){
            if(i<2){
                continue;
            }
            if(isPrime(i)){
                sb.append(i).append('\n');
            }
        }
        System.out.println(sb);
    }
    static boolean isPrime(int a){
        for(int i = 2; i<=Math.sqrt(a); i++){
            if(a%i == 0){
                return false;
            }
        }
        return true;
    }
}

위와 같이 풀었지만, 좀더 효율적인 방법이 없을까 하고 생각해보았다.
M과 N의 최대범위가 1,000,000점을 감안하면, 에라토스테네스의 체를 사용하여 풀면 메모리는 조금 더 먹더라도 시간을 단축 시킬 수 있을 것 같았다.

리팩토링 코드

import java.util.*;
import java.io.*;


public class Main {
    public static boolean[] prime;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        prime = new boolean[N + 1];
        prime[0] = prime[1] = true;
        isPrime();
        for (int i = M; i <= N; i++) {
            if (!prime[i]) {
                sb.append(i).append(" ");
            }
        }
        System.out.println(sb);
    }

    public static void isPrime() {
        for(int i = 2; i<=Math.sqrt(prime.length); i++){
            if(prime[i]){
                continue;
            };
            for(int j = i * i; j< prime.length; j+= i){
                prime[j] = true;
            }
        }
    }
}

---

정리

위의 사진과 같이 소수를 구해야하는 값의 범위 최대치가 크지 않다면, 에라토스테네스의 체 방식이 좀 더 효율 적이라고 할 수있다.
에라토스테네스의 체는 간단히 말해서 2보다 큰 정수들을 같은 정수의 값으로 계속 더한 값들은 소수가 아니므로, 해당 값들을 걸러내는 방식이다. 조금 더 알고싶다면, 에라토스테네스의 체에 대하여 검색해보자.