약수의 개수 구하기

안녕하세요. KataRN 입니다.

 

오늘은 약수의 개수를 구해보겠습니다.

 

 

사실 1부터 N까지의 숫자로 나눠서 나머지가 0인 것을 구하면 됩니다.

 

하지만 코딩테스트를 공부하면서 느낀게 다른 방법이 있으면 알아두는게 좋은것같아서 짧게나마 기록하고자 합니다.

 

제곱근에 소수점이 없으면 약수의 갯수가 홀수고 있으면 짝수입니다.

 

예제 : 프로그래머스 약수의 개수와 덧셈 (https://programmers.co.kr/learn/courses/30/lessons/77884)

import Foundation

func solution(_ left:Int, _ right:Int) -> Int {
    var answer = 0

    for number in left...right{
        if floor(sqrt(Double(number))) == sqrt(Double(number)) {
            answer -= number
        } else {
            answer += number
        }
    }
    return answer
}

 

221126 추가내용)

func cal(_ N : Int) -> Int {
    var i = 1
    var answer = 0
    while i*i <= N {
        if(N % i == 0){
            if(i*i == N){
                answer += 1
            }else{
                answer += 2
            }
        }
        i += 1
    }
    return answer
}

 

위의 코드를 아래처럼 바꾸니 시간초과가 났다...

그냥 위처럼 쓰자...

func cal(_ num: Int) -> Int {
    var count = 0
    let n = Int(sqrt(Double(num)))
    (1...n).forEach {
        if num % $0 == 0 {
            count += 2
        }
    }
    if n * n == num {
        count -= 1
    }   
    return count
}

제곱근까지만 확인해서 2씩 추가하되 5*5처럼 가운데 숫자는 1번만 추가하기 위한 방법.

 

자세한 설명은 아래 블로그가 잘되어있습니다.

https://dev-in-gym.tistory.com/182

[Swift] countFactors 약수구하기 코딜리티 코딩테스트

 

오늘도 짧은 글 읽어주셔서 감사합니다.