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

🔗 백준 1929 - 소수 구하기

문제

알고리즘 분류

• 수학
• 정수론
• 소수 판정
• 에라토스테네스의 체

---

풀이

• 미리 말하자면 이 풀이는 시간 초과로 제출할 수 없다.

1. M, N 입력

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

2. 소수 찾기

• m부터 n까지 1씩 증가시키며 소수를 찾는다.

        for( int i = m ; i < n; i++) { ... }

• (j=2부터 시작하여) i%j == 0이면 소수가 아니므로 반복문을 빠져나옴
• i%j != 0이면 j를 증가시키며 소수인지 확인

            int j = 2;
            while(j < i){
                if(i%j ==0) break;
                else j++;
            }

• 위 과정을 거쳐 j가 계속 증가하다가 i와 같아지면 2부터 i-1 중 나누어떨어지는 수가 없다는 의미(1과 i 자신으로만 나누어떨어짐 = 소수)

            if(j==i)
                System.out.println(i);

전체 코드

import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt(); int n = sc.nextInt();
        for( int i = m ; i < n; i++){
            int j = 2;
            while(j < i){
                if(i%j ==0) break;
                else j++;
            }
            if(j==i)
                System.out.println(i);
        }
    }
}

❌ BUT 위 코드는 시간 초과로 실패 ❌

• 제한 시간 - 2초
  
  

위 풀이의 문제점

• IDEA - 2부터 n-1까지의 수로 나누어떨어지는지 확인하고, 이 중 나누어 떨어지는 수가 있다면 소수가 아니다
• 모든 경우의 수를 확인하며 약수인지 아닌지 확인하므로 시간복잡도는 O(N), 비효율적이다.

---

에라토스테네스의 체

분류에 적힌 <에라토스테네스의 체> 알고리즘으로 풀기로 했다.
에라토스테네스의 체는 대량의 소수를 한 번에, 빠르게 판별할 수 있는 알고리즘이다.

원리

1. 찾고자 하는 범위만큼 배열을 할당하고 값을 넣는다.
2. 2부터 n까지 배수에 해당하는 값을 지운다. (대신 0을 삽입)
3. 남은 수를 출력한다.

아래 블로그에 자세히 설명되어 있다.
🔗 알고리즘 - 에라토스테네스의 체

풀이

1. M, N 입력

• Scanner를 써도 제출은 가능하나, BufferedReader가 더 빠르다.
• StringTokenizer 대신 split함수를 써도 된다.

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        ...
    }

2. n개의 배열을 할당하고 값 삽입 - 배열 초기화

        int[] arr = new int[n+1];
        for( int i = 2; i<=n; i++){
            arr[i] = i;
        }

3. 2부터 n까지 1씩 증가시키며(반복) 배수 삭제

• 0, 1은 반드시 소수가 아니므로 제외
• 이미 0이면 넘어간다.

        for (int i = 2; i<=n; i++){
            if(arr[i] == 0) continue;
            for (int j = i+i; j <= n; j += i) {
                arr[j] = 0;
            }
        }

4. m부터 n까지 남은 수 출력

• 마찬가지로 반복문을 돌 때마다 출력해도 제출은 가능하나, 하나의 문자열로 등록해 한 번에 출력하는 것이 더 빠르다.

        StringBuilder sb = new StringBuilder();
        for(int i = m; i<=n; i++){
            if(arr[i] != 0) sb.append(arr[i] + "\n");
        }
        System.out.println(sb);

전체 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int m = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());

        int[] arr = new int[n+1];
        for( int i = 2; i<=n; i++){
            arr[i] = i;
        }
        for (int i = 2; i<=n; i++){
            if(arr[i] == 0) continue;
            for (int j = i+i; j <= n; j += i) {
                arr[j] = 0;
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i = m; i<=n; i++){
            if(arr[i] != 0) sb.append(arr[i] + "\n");
        }
        System.out.println(sb);
    }
}

• 에라토스테네스의 체 알고리즘의 시간복잡도는 O(NloglogN) 정도이나,배열 할당으로 인해 메모리를 많이 소모해 공간 복잡도 측면에서는 비효율적이라고 한다.