[Swift][Math] 백준 6588번 (골드바흐의 추측)

요구능력 : 소수와 홀수에 대한 이해

 

코드설명 : 

 

문제의 핵심

1. 두개의 홀수

2. 두개의 소수

 

처음에는 에라토스테네스의 체로 소수부분을 모두 구해준다.(동빈나님 블로그에 아주 잘 설명되어있습니다!)

var aa = Array(repeating: 0, count: 1000001)
for i in 2...1000000{
    aa[i] = i
}
for i in 2...1000000{
    if aa[i] == 0{continue}
    for j in stride(from: i + i, through: 1000000, by: i){
        aa[j] = 0
    }
}

 

저는 isGoldBach로 두 홀수 소수의 합으로 나타낼 수 있는 경우에 isGoldBach를 true로 바꿔주고 이곳을 지나지 않는다면 false로 나타낼수 없는 경우로 빼줫습니다.

 

시간을 줄이기 위해서 i를 n/2 +1까지로 했는데 이거보다 더 줄일 방법이 있을겁니다... 저는 그냥 이런식으로 했다.

문제의 조건 두 홀수와 소수의 합입니다.

i를 중심으로 수를 나타낼 것이기 때문에 i가 홀수이고 소수이며 n - i 가 소수여야합니다. (n - i는 어차피 홀수이기 때문에 조건 안넣었습니다. 어차피 n은 짝수가 들어올것이기 때문입니다.)

그리고 방법이 여러가지가 나오게 될건데 여러가지를 없애기위해 break를 해줍니다.

어차피 처음에 i는 작은수부터 시작하고 n - i는 큰수부터 시작되기 때문에  문제에서 b-a가 가장큰것을 출력하라는 조건도 만족합니다.

while true{
    let n = Int(String(readLine()!))!
    if n == 0{
        break
    }
    for i in 3..<((n / 2)+1){
        if i % 2 == 1 && aa[i] != 0 && aa[n - i] != 0 {
            print("\(n) = \(i) + \(n - i)")
            isGoldBach = true
            break
        }
    }
    if !isGoldBach{
        print("Goldbach's conjecture is wrong.")
    }
    isGoldBach = false
}

 

후기 : 원래 수학쪽문제 어렵다고 생각했는데, 다른 카테고리의 어려운문제들을 여러번 풀어보니까

꽤나 쉽게 느껴지는거같은 느낌..?

var isGoldBach = false
//에라토스테네스의 체
var aa = Array(repeating: 0, count: 1000001)
for i in 2...1000000{
    aa[i] = i
}
for i in 2...1000000{
    if aa[i] == 0{continue}
    for j in stride(from: i + i, through: 1000000, by: i){
        aa[j] = 0
    }
}

while true{
    let n = Int(String(readLine()!))!
    if n == 0{
        break
    }
    for i in 3..<((n / 2)+1){
        if i % 2 == 1 && aa[i] != 0 && aa[n - i] != 0 {
            print("\(n) = \(i) + \(n - i)")
            isGoldBach = true
            break
        }
    }
    if !isGoldBach{
        print("Goldbach's conjecture is wrong.")
    }
    isGoldBach = false
}