[Argorithm]소수 판별법

소수란 1과 자기 자신으로만 나누어지는 수를 의미한다.
즉 약수가 2개이다.

📝 소수 판별법

• 사실 소수 판별법도 유클리드 호제법과 비슷하다 그 이유는 소수 판별법도 약수의 개념을 사용하기 때문이다.
• N의 약수의 개수를 세는 방법에는 크게 두가지가 있다.
  • 1부터 N까지의 수로 N을 나눔 O(N)
  • 1부터 루트N까지의 수로 N을 나눔 O(루트N)

 

위의 방법은 모두 특정 숫자 1개를 구하는 방법이다.

그렇다면 특정 구간까지 모두 구한다면 어떻게 될까?

• 기존 시간 복잡도에 x N을 해야할 것이다.
  • 더 좋은 방법을 찾아야 하는 셈이다.

 

📌 에라토스테네스의 체

• 소수를 걸러내는 방법이다.

동작 순서

1. 2부터 N가지 모든 정수를 적는다.
2. 아직 지우지 않은 소수 중 가장 작은 소수를 찾는다. 이 수를 P라고 한다.
3. 아직 지우지 않는 수들 중, P의 배수를 크기 순서대로 지운다.
4. 아직 모든 수를 지우지 않았다면 다시 2번 단계로 돌아간다.

이 방법은 N이 커져도 최대 O(N)에 근접하는 시간복잡도를 보인다.

 

    static boolean[] isPrime;
    
    static void isPrime_fun(int n){ 
        isPrime = new boolean[n+1]; // N번째의 수 까지 받기위해 N+1까지 동적할당
        

        isPrime[0] = isPrime[1] = true; // 0과 1은 소수가 아니니깐 true
        
        for(int i = 2; i <= Math.sqrt(n); i++){ // 2부터 n의 제곱근까지의 모든 수를 확인
            if(!isPrime[i]){ // 해당수가 소수라면, 해당수를 제외한 배수들을 모두 true 처리하기
                for(int j = i*i; j<= n; j += i){//그 이하의 수는 모두 검사했으므로 i*i부터 시작
                    isPrime[j] = true;
                }
            }
        }
    } // isPrime_fun 함수 종료

    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine()); // 소수인지 판별할 숫자 input
        isPrime_fun(N);
    }

 

✔ 키포인트

for(int j = i*i; j<= n; j += i){//그 이하의 수는 모두 검사했으므로 i*i부터 시작
   isPrime[j] = true;
}

이 부분은 왜 i * i로 시작할까? 

• 예를 들어 i = 3인 경우를 생각해보자.
• 3의 배수는 6, 9, 12, 15.....이다.
• 하지만 6은 이미 2의 배수로 처리가 되었으니
• 9가 처음으로 3의 배수로서 처리된다.
• 즉, i * i 이전의 수는 이미 더 작은 소수들의 배수로 처리되었기 때문에 다시 검사할 필요가 없다. 

 

📝 백준 1929번

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

class Main {
    static boolean isPrime[];

    public static void solve(int n){
        isPrime = new boolean[n+1];

        isPrime[0] = isPrime[1] = true;

        for(int i = 2; i <= Math.sqrt(n); i++){
            if(!isPrime[i])
                for(int j = i * i; j <=n; j += i){
                    isPrime[j] = true;
                }
        }
    }
    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());
        solve(n);

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