[알고리즘][백준][JAVA] 1929번 : 소수 구하기

문제 : https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

해당 문제는 범위가 주어지면 범위 내의 소수를 찾아내는 문제인데,

아래 코드와 같이 2중 for문으로 코드를 작성하니 시간 초과가 발생하였다.

// 시간 초과가 발생한 알고리즘

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
//        Scanner sc = new Scanner(System.in);
//        int M = sc.nextInt();
//        int N = sc.nextInt();

        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 num=0;
        int cnt=0;

        for (int i=M;i<=N;i++){
            for (int j=1;j<i;j++){
                if(i%j==0){
                    cnt++;
                }
            }
            if (cnt==1){
                System.out.println(i);
            }
            cnt=0;
        }
    }
}

해당 숫자가 소수인지 찾는데 O(n)의 시간복잡도가 나타나게 되는데, 이를 m의 입력값만큼 반복하니 O(n^2) 의 시간복잡도로 처리 시간이 오래 걸리는 문제가 발생하였다.

 

이는 '에라토스테레스의 체' 라는 소수찾기 알고리즘을 이용해 시간초과 문제를 해결할 수 있다.

처음 들어보았는데, 소수찾기 문제에서는 아주 유명한 알고리즘이었다.

 

간단하게 설명하자면 " 소수가 되는 수의 배수를 지우면 남는 건 소수가 된다. " 라는 알고리즘이며, 

소수가 무엇인지 찾는 것이 아니고 , 2부터 자기 자신을 제외한 배수가 되는 것을 되는 알고리즘이다.

 

알고리즘을 풀어나가는 방식은 두 단계인데, 

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
2. 소수가 되는 수의 배수를 지우면 남는 것은 소수만 된다.

진행 방식은

1. 자기 자신을 제외한 2의 배수를 모두 지운다. (빨간색)
2. 남아 있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다.
3. 자기 자신을 제외한 3의 배수를 모두 지운다. (초록색)
4. 남아 있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다.
5. 자기 자신을 제외한 5의 배수를 모두 지운다. (파란색)
6. 위 과정을 반복한다.

아래 짤을 보면 이해가 쉽다.

출처 : 위키백과

위의 그림의 경우 11^2 > 120이므로 11보다 작은 수의 배수들만 지워도 충분히 구할 수 있다.

120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남은 수는 모두 소수이다.

 

이 원리를 바탕으로 코드를 작성하면 다음과 같다. ( primeNumber 함수)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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());

        primeNumber(M,N);

    }
    static void primeNumber(int m, int n){
        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){	// i의 배수들은 모두 0으로 변경
                arr[j]=0;
            }
        }

        for (int i=m;i<=n;i++){
            if(arr[i]!=0)
                System.out.println(i);
        }
    }
}