chebyshevtheo

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

1. 특정 숫자가 소수인지 아닌지 판별하는 것은 제곱근까지 직접 나누어보는 것이 빠르지만,
2. 특정 범위내의 모든 소수를 구하기 위해서는 에라토스테네스의 체가 O(N log N)으로 더 효율적임
3. 따라서 2부터 2 * n 까지의 모든 소수를 구하고, n + 1 부터 2 * n(n보다 크고 2 * n 보다 작거나 같은) 소수의 개수를 구함으로써 문제를 해결할 수 있음

5. 전체 코드

//
//  main.swift
//  Chebyshevtheo
//
//  Created by 이영재 on 2022/03/08.
//MARK: - chebyshevtheo

//MARK: - Framework
import Foundation

//MARK: - Function
func getPrimeNumberCount(_ number: Int) -> Int {
    var primeNumbers: [Bool] = Array(repeating: true, count: 2 * number + 10)
    var primeNumberCount: Int = 0
    
    primeNumbers[1] = false
    for i in 2...(2 * number) {
        var j: Int = 2
        while i * j <= 2 * number {
            primeNumbers[i * j] = false
            j += 1
        }
    }
    
    for i in number + 1...2 * number {
        primeNumberCount += primeNumbers[i] ? 1 : 0
    }
    
    return primeNumberCount
}

func solution() -> Void {
    var answer: String = ""
    while true {
        //MARK: - Input
        guard let n: Int = Int(readLine() ?? "0") else { return }
        
        //MARK: - Process
        if n == 0 {
            break
        }
        
        answer += "\(getPrimeNumberCount(n))\n"
    }
    
    //MARK: - Output
    print(answer, terminator: "")
}
solution()

 

전체코드는 여기에서 확인할 수 있습니다.