[Algorithm] 에라토스테네스의 체,, 더 이상 헷갈리지 않겠다. (ft. BOJ1929_소수구하기)

민지·2023년 12월 20일

Algorithm

목록 보기

6/8

들어가며

소수인지 판별할 때 쓰이는 방법. 시간복잡도가 작아서 유용하다.

소수인지 판별하는 방법

소수(Prime Number)란?
약수가 1과 자기 자신 뿐인 수.

따라서 특징으로는 1보다 크고 자신보다 작은 어떤 수로 나누었을 때 나머지가 0이 나올 수 없다.

소수인지 판별하는 방법은 두가지가 있다.

1. 정석: 하나씩 수를 보며

위에 특징대로 반복문을 통해 하나씩 수를 살피며 나머지가 0으로 나누어 떨어질 수 있는지 확인하면 된다.

코드

private static boolean isPrimeNumber(int num) {
        for (int i = 2; i <= num; i++) {   
            if(num % i == 0) return false;   
        }
        return true;
    }

시간복잡도

N개의 수를 판별할 때, O(n^2)

2. 에라토스테네스의 체

소수인지 판단할 수 있는 알고리즘이다.

방법

판별할 수 있는 배열을 n+1 크기로 만든 뒤, true로 초기화한다. 0,1은 소수가 아니므로 false 처리를 한다.
2부터 n의 제곱근까지의 반복문을 돌며 소수인지 확인한다.
해당 수가 소수라면, 그 수를 제외한 배수들을 지운다. (그 수를 약수로 가지고 있기 때문)
true로 남은 아이들이 소수이다.

코드

private static void isPrimeNumber() {
        isPrime = new boolean[n+1];
        //일단 true 를 디폴트값으로 설정 후, 아닌 애들을 false 처리하기
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i <= Math.sqrt(n); i++) {   //2~n의 제곱근의 모든 수를 확인한다
            if(isPrime[i]) {    // 이 수가 소수라면, 해당수를 제외한 배수들 모두 false
                for (int j = i*i; j <= n; j+=i) {   //i*i 이 전의 수는 모두 검사된 것이다.
                    isPrime[j] = false;
                }
            }
        }
    }

시간복잡도

N개의 수를 판별할 때, O(n loglogn)

BOJ1929_소수구하기.java

문제보기

정답코드

package solution;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ1929_소수구하기 {
    static int m, n;
    static boolean[] isPrime;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        StringBuilder sb = new StringBuilder();
        // 소수 찾기 -> 에라토스테네스의 체
        isPrimeNumber();
        for (int i = m; i <= n; i++) {
            if(isPrime[i]) sb.append(i).append("\n");
        }
        System.out.println(sb);
    }

    private static void isPrimeNumber() {
        isPrime = new boolean[n+1];
        //일단 true 를 디폴트값으로 설정 후, 아닌 애들을 false 처리하기
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i <= Math.sqrt(n); i++) {   //2~n의 제곱근의 모든 수를 확인한다
            if(isPrime[i]) {    // 이 수가 소수라면, 해당수를 제외한 배수들 모두 false
                for (int j = i*i; j <= n; j+=i) {   //i*i 이 전의 수는 모두 검사된 것이다.
                    isPrime[j] = false;
                }
            }
        }
    }
}