[프로그래머스] 약수의 개수와 덧셈

🔗 출처

약수의 개수와 덧셈 : https://programmers.co.kr/learn/courses/30/lessons/77884

📔 문제설명

두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주세요.

✅ 제한사항

1 ≤ left ≤ right ≤ 1,000

🔍 입출력 예

left	right	result
13	17	43
24	27	52

📝 풀이

어떤 자연수의 약수를 구하는 가장 쉬운 방법은 자연수 N을 i = 1 ~ N 까지 나눠서 나머지가 0으로 나오는 i의 개수를 찾으면 된다.

이러한 경우 최소값 1 ~ 자기자신 N까지 확인하므로 시간복잡도는 O(n) 이 나온다.

더 빠르게

여기서 약수의 특성에 대해서 조금 더 생각해 본다면 항상 약수는 그 짝이 되는 수가 존재한다. (ex. 15 = 3 * 5)

즉, N의 약수들 중 두 약수의 곱이 N이 되는 약수 a,b는 반드시 존재하므로 N의 제곱근까지 약수를 구하면 그 짝이 되는 약수는 자동으로 구했다고 볼 수 있다.

이 방법을 사용하여 약수를 구하면 시간복잡도는 O(n^(1/2)) 이 나온다.

➕ 추가

프로그래머스에서 올린 해설을 찾아보니 애초에 문제에서 요구하는건 모든 약수를 구하는게 아니라 약수의 개수가 짝수인건 더하고 홀수인건 빼는 것이라서 약수가 홀수인지 짝수인지만 구하면 된다.

약수를 구해보면 약수가 홀수라면 그 수는 약수의 제곱수로 나오므로 매개변수 left ~ right 의 제곱수만 구하면 문제를 풀 수 있다.