에라토스테네스의 체를 활용한 소인수분해

 

  어떠한 수 N을 수인수분해한다고 해보자. 예를들어 60 = 2 x 2 x 3 x 5 이다.

 

 

  예를들어 입력값이 아래와 같다면 (첫번째 줄에 N = 소인수분해하려는 수의 갯수, 두번째 줄에 소인수분해하려는 수 kn / N은 1 ~ 1,000,000, kn은 2 ~ 5,000,000)

N
k1 k2 k3...
5
5 4 45 64 54

 

다음과 같이 각각 한줄로 소인수분해한 값을 출력해야 한다고 해보자.

5
2 2
3 3 5
2 2 2 2 2 2
2 3 3 3

 

 

---

  기존에 생각했던 방식은 이하와 같았다. ('더보기')

   내 경우 처음 생각한 방식은, 우선 입력값 N 이하의 모든 소수를 구해두고, 소수 리스트를 순회하며 찾는 방식이었다. 예를들어 N이 60이라면 60 이하의 모든 소수를 우선 구해둔다. 그 후 작은 소수부터 차례대로 나누어떨어지는지 확인하면서 나눠보는 방식이다. getPn은 limit 이하의 모든 소수를 구하는 함수이다. 이후 작은 소수부터 직접 나누어지는지 확인하면서 모든 소수를 확인한다. 어쨌든 2부터 N까지의 모든 수를 직접 나눠보는 것 보다는 더 빠른방법임이 맞지만, 다른 사람들의 코드를 보다가 더 괜찮은 테크닉을 발견했다. 고수분께 여쭤보니 나름 웰논 테크닉이라고 하고, 이후에도 쓸 일이 많을 것 같아 정리해두려고 글을 적게 되었다.

 

private List<Integer> getPn(int limit) {
    List<Integer> pn = new ArrayList<>();
    boolean[] isPn = new boolean[limit+1];
    int sqrtN = (int)Math.sqrt(limit);
    for (int i = 3; i <= sqrtN; i+=2) {
        if (isPn[i]) continue;
        int base = i+i;
        while (base <= limit) {
            isPn[base] = true;
            base+=i;
        }
    }
    pn.add(2);
    for (int i = 3; i <= limit; i+=2) {
        if (!isPn[i]) pn.add(i);
    }
    return pn;
}

public void solution() throws Exception {
    List<Integer> pn = getPn(5000000);
    Set<Integer> set = new HashSet<>(pn);

    int n = Integer.parseInt(br.readLine());
    StringBuilder sb = new StringBuilder();
    StringTokenizer st = new StringTokenizer(br.readLine());
    while (n-->0) {
        int cur = Integer.parseInt(st.nextToken());

        int idx = 0;
        int curPn = pn.get(idx);
        while (curPn <= Math.sqrt(cur)) {
            while (cur % curPn == 0) {
                cur /= curPn;
                sb.append(curPn).append(' ');
            }
            curPn = pn.get(++idx);
        }
        if (set.contains(cur)) {
            sb.append(cur);
        }
        sb.append('\n');
    }
    System.out.print(sb);
}

---

 

 

  더 괜찮은 테크닉은, 미리 어떠한 정수 x에 대해 해당 정수의 가장 작은 소인수를 미리 구해두는 것이다.

예를들어 2의 가장 작은 소인수는 2이고, 100의 가장 작은 소인수는 2, 15의 가장 작은 소인수는 3이다. 이걸 미리 구할 수 있다고 한다면, 위의 코드는 다음과 같이 효율적으로 풀이될 수 있다. 위 처럼 소수를 순회하지 않고, O(1)로 현재 찾고 있는 소인수를 바로 찾을 수 있는거다.

int[] minimumPn = getMinimumPn(5000000);

int n = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
while (n-->0) {
    int cur = Integer.parseInt(st.nextToken());
    while (cur!=1) {
        sb.append(minimumPn[cur]).append(' ');
        cur /= minimumPn[cur];
    }
    sb.append('\n');
}
System.out.print(sb);

 

 

  그럼 이제 각 수의 가장 작은 소인수만 알 수 있으면 되는데, 이것도 에라토스테네스의 체로 가능하다.

private int[] getMinimumPn(int limit) {
    int[] arr = new int[limit+1];
    for (int i = 2; i <= limit; i++) {
        if (arr[i] != 0) continue;

        int base = i;
        while(base <= limit) {
            if (arr[base] == 0)
                arr[base] = i;
            base += i;
        }
    }
    return arr;
}

 

 

관련 문제

백준 16563 - 어려운 소인수분해

백준 3142 - 즐거운 삶을 위한 노력

* 두 문제 모두 위의 2가지 방법을 통과 가능하지만, 자바 기준 시간이 3배 차이난다.