[Swift][Two-Pointer] 백준 1644번 (소수의 연속합)

요구능력

투포인터, 에라토스테네스의 체

 

문제풀이

우선, 에라토스테네스의 체를 이용해서 소수를 판별해주었다.

에라토스테네스의 체를 이용해서 소수를 판별할 때 주의할 점이 있는데,

나는 처음에 에라토스테네스의 체의 배열 개수를 n + 1로 두었다가 97%에서 런타임에러가 나서 최대인 4000001로 설정했다.

 

그리고 투포인터를 이용해서 end를 증가시키면서 end가 소수인경우 더해줬다.

이렇게 하면 연속적으로 소수만 부분합을 구하게된다.

 

가장 중요한점은 start가 소수여야된다는 것이다.

자기자신이 소수가아니라면 continue로 넘겨주었다.

 

후기

투포인터를 살짝 꼬아낸거같다.

 

코드

import Foundation
let n = Int(String(readLine()!))!
var arr = Array(repeating: 0, count: 4000001)
func isPrime(_ number: Int){
    for i in 2...number{
        arr[i] = i
    }
    for i in 2...number{
        if arr[i] == 0{continue}
        for j in stride(from: i+i, through: number, by: i){
            arr[j] = 0
        }
    }
}

isPrime(4000000)
var end = 1
var sum = 0
var count = 0

for start in 1...n{
    if arr[start] == 0{
        continue
    }
    while sum < n && end <= n {
        if arr[end] != 0{
            sum += end
        }
        end += 1
    }
    if sum == n {
        count += 1
    }
    sum -= arr[start]
}
print(count)