문제
- 골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.
짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.
출력
각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다.
풀이
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 이후로 같은 수식이 이어지므로 제곱근 까지 반복해 소수 판별을 하였다.
