이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 112 번째 글 입니다.
목차
실버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()