백준 2581번 소수 - 스위프트(Swift) 풀이

---

 

1. 에라토스테네스의 체를 이용하여 1 이상 10,000 이하의 자연수에 대해 소수 여부를 구한다.
2. M부터 N까지 순회하면서 최소 소수와 소수들의 합을 구한다.

 

1. 에라토스테네스의 체를 이용하여 1 이상 10,000 이하의 자연수에 대해 소수 여부를 구한다.

 에라토스테네스의 체를 이용하면 O(NloglongN)에 1 이상 N이하인 모든 자연수에 대해 소수 여부를 구할 수 있다. N이 최대 10,000이기 때문에 굳이 에라토스테네스의 체를 사용하지 않아도 1~(i-1)까지로 전부 나눠봐서 소수인지 판별하는 O(N^2)을 알고리즘을 사용해도 시간 내에 통과가 가능하다.

 

2. M부터 N까지 순회하면서 최소 소수와 소수들의 합을 구한다.

 M부터 N까지 단순 순회하면서 소수들만 골라 더하고, 처음으로 나오는 소수를 기록해두었다가 출력하면 된다.

반응형

---

import Foundation

var isPrime = Array(repeating: true, count: 10_001)

func findPrimeNumbers() {
    isPrime[1] = false
    
    for i in 2...10_000 {
        guard isPrime[i] else { continue }
        
        var n = i * 2
        while n <= 10_000 {
            isPrime[n] = false
            n += i
        }
    }
}

func solution() {
    let M = Int(readLine()!)!
    let N = Int(readLine()!)!
    
    findPrimeNumbers()
    
    var minPrimeNumber = 10_001
    var primeSum = 0
    
    for i in M...N {
        guard isPrime[i] else { continue }
        if primeSum == 0 { minPrimeNumber = i }
        primeSum += i
    }
    
    if primeSum == 0 {
        print(-1)
    } else {
        print(primeSum)
        print(minPrimeNumber)
    }
}

solution()