Where who wants to meet someone

백준 Swift [4948] 베르트랑 공준 본문

백준 알고리즘 문제 기록/약수, 배수와 소수 2

백준 Swift [4948] 베르트랑 공준

Lust3r 2023. 8. 21. 16:41
728x90

난이도

실버 II

 

문제

https://www.acmicpc.net/problem/4948

 

4948번: 베르트랑 공준

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼

www.acmicpc.net

 

내 답안

import Foundation

var sosu = [Int]()

func test(from valueScope: Int) {
    if valueScope < 2 {
        return
    } else if valueScope == 2 {
        sosu.append(valueScope)
        return
    }

    for i in 2...Int(sqrt(Double(valueScope))) + 1 {
        if valueScope % i == 0 {
            return
        }
    }

    sosu.append(valueScope)
}

while true {
    let input = Int(readLine()!)!

    if input == 0 { break }

    sosu.removeAll()

    for i in (input + 1)...(2 * input) {
        test(from: i)
    }

    print(sosu.count)
}
  • 주어진 것 중 필요한 것은 다음과 같다
    • 자연수 n에 대하여 n보다 크고 2n보다 작거나 같음
    • 입력의 마지막에는 0이 주어짐
    • 첫 번째 범위에 해당하는 소수의 개수를 출력
  • 1) 이전에 썼던 방식처럼 필요한 로직을 메서드로 분리하여 시간초과가 나지 않도록 조치
    2) 입력받은 값(input)이 0이면 while 루프 종료
    3) 0이 아니라면 소수의 개수를 알아야 하니 sosu 배열을 초기화(removeAll)
    4) for문을 통해 주어진 범위(n < i <= 2n)를 돌며 test 메서드 호출
    5) test 메서드에서는 인자값이 2보다 작으면 return, 2라면 sosu에 추가 후 return을 우선 수행
    6) 5번의 경우가 아니라면 루트 n까지의 범위로 나누어서 나뉘어지는 값이 있는지 판별
    7) 나뉘어지는 값이 있다면 소수가 아니기 때문에 return, 없다면 sosu에 추가
    8) 4번의 범위가 끝나면 sosu에 들어간 요소의 수를 출력

 

저작자표시 비영리 변경금지

'백준 알고리즘 문제 기록 > 약수, 배수와 소수 2' 카테고리의 다른 글

백준 Swift [13909] 창문 닫기  (0) 2023.08.21
백준 Swift [17103] 골드바흐 파티션  (0) 2023.08.21
백준 Swift [1929] 소수 구하기  (0) 2023.08.18
백준 Swift [4134] 다음 소수  (0) 2023.08.18
백준 Swift [2485] 가로수  (0) 2023.08.17
'백준 알고리즘 문제 기록/약수, 배수와 소수 2' Related Articles more