BOJ - 소수상근수(9421)

실버1 : 수학 문제이다.

풀이

에라토스 테네스를 적용한 수를 가져오고, 이를 기반으로 상근수 로직을 적용하여 답을 계산한다.

Code

//
//  main.swift
//  CodingTest
//
//  Created by 최완식 on 2021/08/15.
//
 
import Foundation
 
// 에라토스의 체를 통해서 들어온 input보다 작거나 같은 소수들을 측정한다.
// 소수인 친구들에 대해서 상근수 인지 판단한다.
 
func seiveOfEratosThenes(_ number: Int) -> Array<Bool> {
    var array = Array.init(repeating: true, count: number+1)
    array[0] = false
    array[1] = false
 
    for i in 2...Int(sqrt(Double(array.count))) {
        if array[i] == true {
            for j in stride(from: i*2, through: number, by: i) {
                array[j] = false
            }
        }
    }
    return array
}
 
func calculate(_ number: Int) -> Int {
    let numString = "\(number)"
    let sum = numString.reduce(0, { $0 + pow(Double($1.wholeNumberValue!), 2)  })
    return Int(sum)
}
 
func numberOfSanguen(_ number: Int) -> Bool {
    var curr = number
    var bucket = Set<Int>([curr])
    
    while true {
        let next = calculate(curr) // 값 계산
        if next == 1 { return true } // 1인지 확인 -> Return true
        if bucket.contains(next) { return false } // 이미 나왔던 것에 있는지 확인 -> return False
        
        bucket.insert(next) // 현재 계산 된 것 기록
        curr = next // 값 업데이트
    }
}
 
func main() {
    let input = Int(readLine()!)!
//    let input = 20
    let primeArray = seiveOfEratosThenes(input).enumerated().filter({ $0.element == true }).map({ $0.offset })
    
    primeArray.filter({ numberOfSanguen($0) }).forEach { print($0) }
    
}
main()
 

Reference

• 백준(9421번) - 소수상근수