[알고리즘] 정수론 - 소수에 관하여

 

소수란, 1과 자기 자신 이외의 값으로는 나누어 떨어지지 않는 수를 뜻한다.

우리는 이 소수를 구하기 위해서, 통상적으로 2부터 자기 자신 바로 이전이 될 때까지 나누어 떨어지는 지 확인하곤 한다.

하지만, 이러한 방식은 대량의 소수를 구해야 할 때 꽤나 많은 시간 복잡도를 소요한다.

 

 

 

그래서 많은 똑똑한 사람들이 수학적으로 소수를 구할 수 있는 효율적인 방법을 찾아냈다.

그 중 하나가 "에라토스테네스의 체"이다.

 

 

 

에라토스테네스의 체
: 소수의 배수를 소거하는 방법으로 소수를 찾아내는 방법

 

 

에라토스테네스의 체를 사용할 때, 시간복잡도는 이중 for문을 사용하므로 O(N^2)이라고 판단할 수 있다.

꽤 많은 것이 아니냐 생각할 수 있는데, 바깥쪽 for문을 생략하는 경우가 많아 실제론 O(Nlog(logN))이라고 할 수 있다.

 

 

 

 

 

 

 

에라토스테네스 체 사용 예제 1

 

 

백준 1929번 문제를 통해 소수를 쉽고 빠르게 구할 수 있는 방법을 알아보자.

 

1929번: 소수 구하기

 

문제에서는 대량의 소수를 출력하는 것을 요구한다. 그렇다. 에라토스테네스의 체를 사용하기 가장 적합한 것이다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        ArrayList<Boolean> primeList;

        primeList = new ArrayList<Boolean>(N + 1);


        primeList.add(false);
        primeList.add(false);


        for (int i = 2; i <= N; i++) {
            primeList.add(i, true);
        }

        for (int i = 2; (i * i) <= N; i++) {
            if (primeList.get(i)) {
                for (int j = i * i; j <= N; j += i)
                    primeList.set(j, false);
            }
        }

        for (int i = M; i <= N; i++) {
            if (primeList.get(i)) {
                bw.write(i + "\n");
            }
        }

        bw.flush();
        br.close();
        bw.close();
    }
}

 

소수 여부를 저장하기 위한 배열 primeList를 만든다.

이후, 전부 소수 true로 설정해 주고 에라토스테네스의 체를 통해 소수가 아닌 것을 걸러준다.

 

- 첫번째 for문에서, 2부터 N의 제곱근까지 수행한다. 그 이유는 N보다 작은 숫자는 항상 그 제곱근까지 약수를 가질 수 있기 때문이다. (예를 들어 16 = 4*4인데, 16보다 작은 값은 그 보다 작은 숫자로 약수를 가진다.)

- 두 번째 for문은 i+i부터 N까지 i씩 더하며 그 배수를 걸려준다.

 

 

 

 

 

 

 

 

에라토스테네스 체 사용 예제 2

 

백준 1456번 문제를 통해 에라토스테네스에 익숙해져보자.

1456번: 거의 소수

 

 

범위 내의 소수를 모두 구하고, 해당 소수의 제곱의 범위가 Min과 Max사이에 위치하는 지 구하는 문제이다.

 

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        long min = sc.nextLong();
        long max = sc.nextLong();

        long[] A = new long[10000001];
        for(int i=2; i<A.length; i++) {
            A[i] = i;
        }

        for(int i=2; i<=Math.sqrt(A.length); i++) {
            if (A[i] == 0) {
                continue;
            }

            for(int j = i+i; j<A.length; j=j+i) {
                A[j] = 0;
            }
        }
        int count = 0;
        for(int i=2; i<10000001; i++) {
            if (A[i] != 0) {
                long temp = A[i];
                while((double)A[i] <= (double)max/(double)temp) {
                    if ((double)A[i] >= (double)min/(double)temp) {
                        count++;
                    }
                    temp = temp * A[i];
                }
            }
        }

        System.out.println(count);


    }
}

 

 

- 에라토스테네스의 체를 구현하는 부분 아래 범위를 체크하는 코드를 보자. 해당 부분에서는 제곱을 통해 long 범위를 벗어나는 것을 막기 위해서, 식을 적절히 처리했다.(곱하기 대신 나누기 사용)

- n 제곱을 구현하기 위해서 temp = temp * A[i]를 사용했다.

 

 

 

 

 

 

 

 

에라토스테네스 체 사용 예제 3

 

이 문제는 에라토스테네스의 체와 팰린드롬 수를 적절히 사용한 예제이다.

에라토스테네스를 통해 소수를 구하고, 해당 값에서 팰린드롬 검사를 진행하는 식이다.

 

1747번: 소수&팰린드롬

 

 

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] A = new int[10000001];

        // 최대 범위에 해당하는 모든 소수를 구해 놓음
        // for(1000000만큼 반복)
        // -> 소수 집합 초기화
        for(int i=2; i<A.length; i++) {
            A[i] = i;
        }

        // for(10^3만큼 반복)
        // -> 소수 체크
        for(int i=2; i<=Math.sqrt(A.length); i++) {
            if (A[i] == 0) {
                continue;
            }

            for(int j=i+i; j<A.length; j=j+i) {
                A[j] = 0;
            }
        }

        int i=n;
        while(true) {
            if (A[i] != 0) {
                int result = A[i];
                if (isPalindrome(result)) {
                    System.out.println(result);
                    break;
                }
            }
            i++;
        }

    }
    private static boolean isPalindrome(int target) {
        char[] temp = String.valueOf(target).toCharArray();

        int s = 0;
        int e = temp.length - 1;

        while(s<e) {
            if (temp[s] != temp[e]) {
                return false;
            }
            s++;
            e--;
        }
        return true;
    }
}

 

 

- 에라토스테네스의 체를 통해서 소수를 구하는 코드는 이전과 같이 구할 수 있다.

- 펠린드롬 수를 찾기 위해서, 자바의 String.valueOf(target).toCharArray() 를 사용했다.

- start인덱스와 end 인덱스를 사용하는 투 포인터를 통해 팰린드롬 수임을 검증했다.

 

 

 

 

 

 

에라토스테네스 체 사용 예제 4

 

이 문제는 사실 상 소수를 구하는 문제는 아니지만, 제곱 수를 구하는데 있어 비슷한 알고리즘을 사용한다.

범위 내에 여러 제곱 수 를 찾는데, for문 두개를 사용한다.

 

1016번: 제곱 ㄴㄴ 수

 

 

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        long min = sc.nextLong();
        long max = sc.nextLong();

        boolean[] check = new boolean[(int)(max-min+1)];

        for(long i=2; i*i<=max; i++) {
            long pow = i*i;
            long start_index = min/pow;
            if  (min % pow != 0) {
                start_index++;
            }
            for(long j=start_index; pow*j <= max; j++) {
                check[(int)((j*pow) - min)] = true;
            }
        }
        int count = 0;
        for(int i=0; i<=max-min; i++) {
            if (!check[i]) {
                count++;
            }
        }
        System.out.println(count);
    }

}

 

- 찾는 범위의 최소 값을 반영해주기 위해 start_index를 사용했다. (나누기를 사용하여 처리)

- start_index부터 제곱수와 곱해주며 제곱 수가 되는 값을 처리해 준다.

 

 

 

 

 

Reference

- Do it! 코딩 테스트 - 기초 편