BOJ-17103 골드바흐 파티션 Swift

문제

• 골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.

짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.

입력

첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.

출력

각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다.

풀이

1. 2부터 주어진 수 N까지의 소수를 찾는다.

2. 반복문을 통해 2부터 N / 2 까지 파티션 수 찾아서 갯수 출력한다.

 

처음에 Set, Dictionary 여러가지 사용을 해봤는데 계속 시간초과가 떴다.

<시간초과가 뜬것 중 하나의 코드>

import Foundation

func isPrimeNum (num: Int) -> Bool {
    if num < 2 {
        return false
    } else {
        var idx = 2
        while idx * idx <= num {
            if num % idx == 0 {
                return false
            } else {
                idx += 1
            }
        }
        return true
    }
}

let count = Int(readLine()!)!

for i in 0..<count {
    var num = Int(readLine()!)!
    var set = Set<Int>()
    var result = 0
    
    for j in 2..<num {
        var sub = num - j
        if set.contains(j) {
            continue
        } else {
            if isPrimeNum(num: j) && isPrimeNum(num: sub) {
                set.insert(j)
                set.insert(sub)
                result += 1
            }
        }
    }
    print(result)
}

소수 판별하는법

1. 정수 N을 2부터 N-1까지 나눠서 나누어 떨어지지 않으면 정수 N은 소수다. ( O(n) )

2. 정수 N을 2부터 N / 2 까지 나누어 떨어지지 않으면 정수 N은 소수다 .( 1/2N -> O(n) )

3. 정수 N을 2부터 √N 까지 나누어 떨어지지 않으면 정수 N은 소수다. ( O(√N) )  ** 제일 효율적이다 **

 

정수 N까지의 소수들을 구할 때 for i in 2..<N 까지 3번을 이용해서 소수를 구했었는데, 이게 시간초과의 원인이 되었던것 같다.

소수인지 판별하고, 소수들을 구할때는 에라토스테네스의 체 를 이용했다

 

에라토스테네스의 체

1. 정수 N이 주어졌을 때, 1부터 N까지 나열한다.

2. 1은 지운다.

3. i = 2 , i부터 √N 까지 i의 배수를 지워나간다. (i 는 제외한다.)

 i = 2 일때, 4 6 8 10 ... 2i

 i = 3 일때, 6 9 12 15 ... 3i

---

 i = n 일때, 2n 3n 4n ... n^2

4. 더이상 지울 수 없을 때 까지 지운다.

 

 

예시)

18까지의 소수를 구할 때 √18 = 4.24264068712...

1	2	3	4	5	6
7	8	9	10	11	12
13	14	15	16	17	18

 

1. 1을 지운다

	2	3	4	5	6
7	8	9	10	11	12
13	14	15	16	17	18

 

2.  2를 제외한 2의 배수를 지운다.

	2	3	4	5	6
7	8	9	10	11	12
13	14	15	16	17	18

 

3.  3를 제외한 3의 배수를 지운다.

	2	3	4	5	6
7	8	9	10	11	12
13	14	15	16	17	18

 

4.  4를 제외한 4의 배수를 지운다.

	2	3	4	5	6
7	8	9	10	11	12
13	14	15	16	17	18

 

5. 나머지남은 수의 배수는 정수 N보다 크기 때문에 스킵

-> 2부터 18까지의 소수는 2, 3, 5, 7, 11, 13, 17

 

에라토스테네스의 체 알고리즘의 시간복잡도는  O(NloglogN)으로 선형시간에 가깝다.

하지만 많은 메모리가 필요하기 때문에, 10억이상의 소수를 찾는 매우 높은 수 에서는 사용하기 어렵다.

 

<정답 코드>

import Foundation

func primeNums (num: Int) -> [Int] {
    var arr = Array(0...num) // 정수 num까지 나열
    var count = Int(sqrt(Double(num))) + 1
    arr[1] = 0  // 1을 지운다.
    for i in 2..<count {    //정수 num의 제곱근까지 배수를 지운다.
        if arr[i] != 0 {
            var idx = 2
            while idx * i <= num {
                arr[idx * i] = 0
                idx += 1
            }
        }
    }
    return arr
}

let count = Int(readLine()!)!

for i in 0..<count {
    var num = Int(readLine()!)!
    let set = primeNums(num: num)
    var result = 0
    
    for j in 2...num / 2 { 
        let sub = num - j
        if set[j] != 0 {
            if set[sub] != 0 {
                result += 1
            }
        }
    }
    print(result)
}

 

제곱근까지 반복한이유

예시) 20의 약수

• 1 x 20 = 20
• 2 x 10 = 20
• 4 x 5 = 20
• 5 x 4 = 20
• 10 x 2 = 20
• 20 x 1 = 20

이렇게 나타냈을때 1 x 20 = 20  <=> 20 x 1 = 20 으로 대칭 구조를 이루고있다.

따라서 √20 = 4.472135955 으로 4 이후로 같은 수식이 이어지므로 제곱근 까지 반복해 소수 판별을 하였다.