알고리즘 - 소수 구하기

 

1. 개요

 

소수는 Prime number, 즉 1과 자기 자신 이외에는 약수를 갖지 않는 수를 의미한다.
예를 들면, 2, 3, 5, 7, 11, 13, 17, 19 등의 숫자를 통해 알 수 있다.

이러한 소수를 코드를 통해 찾아낼 수 있다면 어떨까? 이에 대해서는 여러가지 방법이 있다. 그 중 가장 성능이 좋은 방법들까지 천천히 알아보자.

만약, 1~10만 까지의 숫자 중 소수를 모두 찾으라고 하면 성능이 좋지 않다면 시간이 오래 걸릴 것이다. 따라서 좋은 성능으로 소수를 찾는 법도 알아두는 것이 좋다.

 

[방법]

① 1부터 [해당 숫자 / 2] 까지 나누어 나누어지는지 직접 확인하는 것이다. ([] 는 가우스 기호이다.)
② 현재 해당 숫자보다 작은 소수들로만 나누어서 판별한다.
③ 현재 숫자가 K라면 루트 K까지의 소수로만 나누어서 확인한다.
④ 2, 3, 5이후에는 6n+1 / 6n+5 중 하나만 소수이므로 이를 통해 구한다. (미사용)
⑤ 에라토스테네스의 체를 사용한다.
 

 

①의 방법은 이해하기 쉽다. 현재 값이 53라면 2로 나눈 값 중 가우스 기호의 결과값은 21이다. 즉, 21까지만 확인하여 나누어보고 53이 소수인지 판별하는 것이다. ( 왜 2로 나눈 값 까지인지는 명확하니 설명 생략.. )

이 방식은 그러나 시간복잡도가 O((N/2)^2) 까지 걸릴 수 있다. (반복문 중복해 사용)

 

②는 왜 그런가? 사실상 짝수는 모두 2의 배수이다. 따라서, 2는 소수이므로 2보다 큰 짝수는 2로 나누어 소수가 아님을 알 수 있다.
홀수의 경우에도 3, 5, 7 등의 소수의 배수로써 설정되기 때문에 소수로만 나누어봐도 알 수 있게 된다.

예) 15  = 3 * 5 / 27 = 3 * 9 등..

이 또한, 시간복잡도는 정확히 구하기 어려우나 최적의 성능을 내는 방식은 아니다.

 

③ 왜 루트 K 까지만 구하면 될까?

값 N = a * b 라고 가정하자. 그럼 a < b라면 a < √N  이고 √N  < b가 반드시 성립한다. ( 둘 다 더 작거나 더 크면 N = a * b 가 될 수 없기 때문)

따라서, 더 작은 쪽의 숫자와만 비교해 약수가 없으면 되므로, √N 까지만 비교하면 되는 것이다.

이 방식은 시간복잡도가 O(√N )이 된다.

 

④는 특이하다. 2, 3, 5를 제외한 모든 소수는 사실 6n+1 / 6n+5로 거의 찾을 수 있다. 하지만 이는 반드시 적용되는 법칙이 아니다. 25와 같은 예외 사항들이 있기 때문에 여기서 별도로 사용하지 않도록 한다.

다만, 아래의 에라토스테네스의 체를 이 방식을 이용해 좀 더 빠르게 구현할 수도 있기는 하다. 다만 이론상으로 6배 더 빨라져야 하나 실제로 구현해보면 그만큼의 성능이 나오지는 않는다.(백준 알고리즘 강의 참조)

 

⑤ 에라토스테네스의 체는 다음의 그림으로 대체한다.

에라토스테네스의 체, 위키백과

그림만 봐도 쉽게 이해할 수 있다. 2를 제외한 2의 배수를 모두 지우고, 3을 제외한 3의 배수를 모두 지워서 그 중 나머지 지워지지 않은 값들을 소수로 인식하는 방식이다.(이미 지운 것은 통과)

그림에서는 7을 제외한 7의 배수까지만 모두 지우면 된다. 위 에라토스테네스의 체는 자기 자신의 제곱부터 지워나간다고 보면 되는데, 왜냐면 자기 자신과 자신 보다 작은 값으로 곱해진 배수는 이미 이전에 지워짐이 확실히 보장되기 때문이다.

예를 들어, 다음으로 체크할 수는 11인데(8, 9, 10은 앞에서 지워짐) 11 * 10 까지는 이미 이전에 모두 지워진 상태이다. 그러므로 11 * 11을 지워야 하는데 위 그림은 120이 끝이고 11 * 11 = 121이므로 11부터는 체크하지 않아도 된다.

이 에라토스테네스의 체는 굉장히 연산속도가 빠르기 때문에 사실상 가장 성능이 좋은 방식이다.

 

 

2. 코드로 구현하기(시간 계산해보기)

 

package com.test;

import java.io.IOException;
import java.util.ArrayList;

public class Main {
    public static void GetPrime(String[] args) {
        // 소수점 개수 구하기
        long start = System.currentTimeMillis();
        getPrime1(100000);
        long end = System.currentTimeMillis();
        System.out.println("① 수행 시간 : " + (end - start));
        System.out.println();

        start = System.currentTimeMillis();
        getPrime2(100000);
        end = System.currentTimeMillis();
        System.out.println("② 수행 시간 : " + (end - start));
        System.out.println();
        
        start = System.currentTimeMillis();
        getPrime3(100000);
        end = System.currentTimeMillis();
        System.out.println("③ 수행 시간 : " + (end - start));
        System.out.println();

        start = System.currentTimeMillis();
        getPrime5(100000);
        end = System.currentTimeMillis();
        System.out.println("⑤ 수행 시간 : " + (end - start));
    }


    // ① 가장 단순하게 2를 제외한 모든 홀수를 테스트하되, 자신에서 2를 나눈 값 중 가장 큰 자연수로 까지만 테스트하는 경우
    public static void getPrime1(int end){
        int count = 1; // 2는 세고 시작

        // 3부터 2씩 더해서 홀수만으로 테스트
        for(int i=3; i <= end; i+=2){
            boolean isPrime = true;
            for(int j=2; j <= i/2; j++){
                // 0으로 나누어진다면 소수가 아니므로 그만둠.
                if(i % j == 0){
                    isPrime = false;
                    break;
                }
            }
            // 소수라면 count++
            if(isPrime){
                count++;
            }
        }
        System.out.println("소수의 개수 : " + count);
    }

    // ② 현재 해당 숫자보다 작은 소수로만 나누어서 판별하는 경우
    public static void getPrime2(int end){
        // 소수의 값을 저장하는 array list
        ArrayList<Integer> list = new ArrayList<>();
        list.add(2); // 2는 소수에 바로 넣어줌
        int count = 1;

        for(int i=3; i <= end; i+=2){
            boolean isPrime = true;
            for(int val : list){
                // 0으로 나누어진다면 소수가 아니므로 그만둠.
                if(i % val == 0){
                    isPrime = false;
                    break;
                }
            }
            // 소수라면 count 늘리고 소수 저장
            if(isPrime){
                count++;
                list.add(i);
            }
        }
        System.out.println("소수의 개수 : " + count);
    }

    // ③ 현재 해당 숫자의 루트값 이하의 소수까지로만 나누어서 확인
    public static void getPrime3(int end){
        // 소수의 값을 저장하는 array list
        ArrayList<Integer> list = new ArrayList<>();
        list.add(2); // 2는 소수에 바로 넣어줌
        int count = 1;

        for(int i=3; i <= end; i+=2){
            boolean isPrime = true;
            for(int val : list){
                // 0으로 나누어진다면 소수가 아니므로 그만둠.
                if(i % val == 0){
                    isPrime = false;
                    break;
                }
                // val의 제곱이 더 크다면 더 이상 수행하지 않아도 된다.
                if(val * val > i){
                    break;
                }
            }
            // 소수라면 count 늘리고 소수 저장
            if(isPrime){
                count++;
                list.add(i);
            }
        }
        System.out.println("소수의 개수 : " + count);
    }

    // ⑤ 4는 건너 뛰고, 에라토스테네스의 체를 사용하기
    public static void getPrime5(int end){
        int count = 0;
        // 해당 위치의 index가 true면 소수가 아니라는 의미로 사용
        boolean check[] = new boolean[end+1];

        for(int i=2; i <= end; i++){
            // check[i]가 true면 소수임
            if(check[i] == false){
                count++;
                // i*i부터 시작해 i를 더해가며 아닌 것들을 모두 제외시킴
                // 숫자가 커서 overflow가 날 수 있어 1보다 크다는 조건 추가
                for(int j= i*i; j > 1 && j <= end; j+=i){
                    check[j] = true;
                }
            }
        }
        System.out.println("소수의 개수 : " + count);
    }
}

 

이 각각의 계산 결과는 다음과 같다.

 

소수의 개수 : 9592
① 수행 시간 : 2087

소수의 개수 : 9592
② 수행 시간 : 565

소수의 개수 : 9592
③ 수행 시간 : 31

소수의 개수 : 9592
⑤ 수행 시간 : 8

Process finished with exit code 0

 

실제로 확인해보면 에라토스테네스의체가 정말 굉장히 빠르다는 것을 알 수 있다. 이 시간은 필자의 컴퓨터의 성능에 따라 영향을 받으므로 다른 컴퓨터에서는 다르게 나올 수 있다.

 

관련 백준 알고리즘 문제

백준 1929번 : www.acmicpc.net/problem/1929

백준 1978번 : www.acmicpc.net/problem/1978

백준 6588번 : www.acmicpc.net/problem/6588
백준 17103번 : www.acmicpc.net/problem/17103 
 - 이 2개는 골드바흐 추측 문제임. 소수만 빠르게 구하면 쉽게 풀 수 있다.

 

 

긴 글 읽어주셔서 감사드리며, 피드백을 댓글로 주시면 반영하도록 하겠습니다.

감사합니다.