20180606 소수 (Prime Number)

소개

• Prime Number 라고 부른다.
• 자신보다 작은 두 개의 자연수를 곱하여 자신을 만들 수 없는 수여야 한다. (단 1은 제외)
  e.g. 8 = 2 * 4 = 1 * 8
  e.g. 7 = 7 * 1
• 1과 자신 이외의 수로 나눌 수 없는 자연수

" 모든 양의 정수는 유일한 소인수분해를 갖는다 " 라는 산술의 기본정리에 의해서, 모든 자연수는 한가지 방법으로 소수의 곱을 표현할 수 있으며 이를 소인수 분해의 일의성이라고 한다. 결국 곱셈의 관점에서 소수는 자연수를 이루는 성분이다. 여기서 1은 소수의 특징을 받지 못하는데 너무 깊게 들어가면 나도 모른다.

일의성

어떤 정의로 정하여진 것이 하나밖에 없는 성질 또는 어떤 조건을 채우는 것이 오직 하나밖에 없는 성질. 예를 들면 두 수 a, b 의 합은 오직 a + b 이며, 일차 방정식의 근은 오직 하나밖에 없다.

여튼 소수는 무한하게 많다. 유클리드 증명은 아래와 같이 말한다.

서술된 증명 내용

유한 개의 소수가 존재한다고 가정한다. 

이 유한 개의 소수들을 모두 곱한 값에 +1 을 한다면 그 결과값은 다른 어떤 소수로 나누어도 나머지가 1이므로 결국 어떠한 소수로도 나누어지지 않는다. 따라서 이 수가 소수라면 기존의 최대소수보다 큰 소수가 있다는 것이 증명되는 것이고, 이 수가 소수가 아니라고 해도 또 다른 소수가 있어야한다는 것을 의미한다. 결국 소수가 유한하다는 가정은 애초에 모순이 존재함을 파악하다. 

소수 구하기 (JAVA)

소수를 구하는 방법은 굉장히 많지만 보편적으로 많이들 이용하는 에라토스테네스 체에 대해 알아보려고 한다. 수의 범위가 1 ~ 100000 이라고 가정한 상태에서 해당 범위내의 소수를 모두 구하는 내용을 해보자. 에라토스테네스 체에 대한 자세한 설명은 위키를 참고하고 코드상에서는 (3) 과 (4) 구현되어 있다.

(1) O(N^2) 방식

public static void process1(){
    boolean[]primeNumber = new boolean [100001];
    Arrays.fill(primeNumber, true);
    
    primeNumber[1] = false;
    
    for (int number = 2; number < primeNumber.length; number++) {
        for (int div = 2; div < number; div++) {
            if (number % div == 0) {
                primeNumber[number] = false;
                break;
            }
        }// for
    }// for
}

2 ~ 10000 까지의 소수는 1과 자기자신을 제외한 수로 나누어떨어진다면 소수가 아님을 판별하는 것이다. 애초에 불린타입의 배열은 전체 true 이고, 이후에 소수가 아님을 판별하면서 if 문내에서 false 를 해주었다.

(2) 최적화 1 : 산술의 기본정리 이용

public static void process2(){
    boolean[]primeNumber = new boolean [100001];
    Arrays.fill(primeNumber, true);
    
    primeNumber[1] = false;
    
    ArrayList<Integer> primeList = new ArrayList<Integer>();
 
    for (int number = 2; number < primeNumber.length; number++) {
        if (primeList.size() != 0) {
            for (int i = 0; i < primeList.size(); i++) {
                if (number % primeList.get(i) == 0) {
                    primeNumber[number] = false;
                    break;
                }
            }
        }
        
        if(primeNumber[number]){
            primeList.add(number);
        }
    }// for
}

2 ~ 10000까지 소수를 구하지만 1과 자기자신을 제외함과 더불어서 추가로 자연수는 소수로 이루어져 있음으로 다른 소수로 나누어지는지 확인한다. 가령 16을 예시로 들자

16 = 1 * 16 = 2 * 8 = 4 * 4 = 8 * 2 = 16 * 1 이다.

이 내용에서 16은 소수 2로 나누어떨어지기 때문에 16은 소수가 아님을 알 수 있는 것이다. 이전보다 코드의 연산 횟수가 확연히 줄어든다.

(3) 최적화 2

public static void process3(){
    boolean[]primeNumber = new boolean [100001];
    Arrays.fill(primeNumber, true);
    
    primeNumber[1] = false;
    
    for(int i = 2; i < primeNumber.length; i++){
        if(primeNumber[i]){
            int mul = 2;
            int value = 0;
            
            while(true){
                value = i*mul;
                
                if(value < primeNumber.length){
                    // 자연수는 소수로
                    if(primeNumber[value])
                        primeNumber[value] = false;
                }
                else break;
                
                mul++;
            }
        }
    }
}

소수의 배수는 모두 제거하는 방법이다. 2의 배수 전체 제거, 3의 배수 전체 제거, 4의 배수 제거, 이렇게 쭉쭉 가는 형태이다.

(4) 최적화 3

public static void process4(){
    boolean[]primeNumber = new boolean [100001];
    Arrays.fill(primeNumber, true);
    
    primeNumber[1] = false;
    
    int sqrtValue = (int)Math.sqrt(primeNumber.length-1);
 
    for(int i = 2; i <= sqrtValue; i++){
        if(!primeNumber[i])
            continue;
        
        for(int j = i+i; j < primeNumber.length; j += i){
            primeNumber[j] = false;
        }
    }
}

public static void process4(){
    boolean[]primeNumber = new boolean [100001];
    Arrays.fill(primeNumber, true);
    
    primeNumber[1] = false;
    
    int sqrtValue = (int)Math.sqrt(primeNumber.length-1);
 
    for(int i = 2; i <= sqrtValue; i++){
        if(!primeNumber[i])
            continue;
        
        for(int j = i*i; j < primeNumber.length; j += i){
            primeNumber[j] = false;
        }
    }
}

두 개의 코드를 동시에 올렸는데 13번째 줄을 보면, for() 구문 내의 i+i 와 i*i 로 되어있다. i*i 가 되는 이유는, j = (2 * i) (3 * i) (4 * i) ... (i * i-i) 인 구간은 미리 다 돌았기 때문이다. 2i는 2의 배수이므로 이미 확인이 되었고, 3i도 3의 배수로 확인되었기 때문이다. 결과적으로 배수로써 모두 파악이 완료되어있기 때문에 불필요한 연산의 소모를 줄일 수 있다.

결국 시간복잡도 점근적표기는 크게 바뀌지 않더라도 실행시간을 줄어드는것을 확인할 수 있다. 

깃헙소스

[ 참고링크 ]

[ 소수 ]

[ 에라토스테네스 체 ]