Python

파이썬 약수의 개수 구하기(제곱근, 루트)

Created by
  • 서경태
Created at
주어진 숫자의 약수가 짝수면 + 홀수면 - 하는 문제에서 나는 약수를 구하는데 굉장히 원초적인 방법을 사용했다.
k_lst = []
for k in range(1,n+1):
if n % k == 0:
k_lst.append(k)
# print(len(k_lst))
if len(k_lst) % 2 == 0:
result = 'even'
else:
result = 'odd'
이렇게 주어진 숫자를 1부터 한번씩 다 대입해서 약수들을 리스트로 만들고 더한 값이 홀수 인지 짝수인지 판단하는 것이다.
실제 문제는 left와 right 두 숫자가 주어져 그 사이의 숫자들을 구하고 약수의 개수에 따라 +,-를 부여해 합산하는 것이기에 반복문을 4번이나 돈 것이다.
다른 사람들의 풀이를 보니 약수의 특징을 이용해 더 쉽게 문제를 풀 수 있었다.
약수가 홀수인 숫자는 루트했을때 정수인 특징이 있다.
예를 들어, 16은 1, 2, 4, 8, 16으로 총 5개의 약수를 가지는데 16의 루트는 4이다.
반대로 12는 1, 2, 3, 4, 6, 12로 총6개의 약수를 가지는데 12의 루트는 3.4641...이다.
이처럼 주어진 숫자에 루트를 씌워 나온 값이 정수이면 그 숫자의 약수는 홀수이고 정수가 아니라면 그 숫자의 약수는 짝수인 것이다.
코드로 작성하면 이렇게 된다.
def solution(left, right):
answer = 0
for i in range(left,right+1):
if int(i**0.5)==i**0.5:
answer -= i
else:
answer += i
return answer
left부터 right까지 숫자를 구한다음 그 숫자들을 반복문을 통해 약수의 개수가 홀수인지 짝수인지 구분하고 더하기 빼기를 진행한다.
파이썬에서 루트는 n**0.5 혹은 n**(1/2)를 사용하거나 math 모듈에서 sqrt를 사용한다.
math.sqrt(n) sqrt는 square root의 약자다.
내가 작성한 코드에 비하면 너무나 효율적이다.
내가 작성한 코드:
def solution(left, right):
lst = [i for i in range(left , right+1)]
even_lst = []
odd_lst = []
for j in lst:
result = even_or_odd(j)
if result == 'even':
even_lst.append(j)
else:
odd_lst.append(j)
return sum(even_lst) - sum(odd_lst)
def even_or_odd(n):
k_lst = []
for k in range(1,n+1):
if n % k == 0:
k_lst.append(k)
# print(len(k_lst))
if len(k_lst) % 2 == 0:
result = 'even'
else:
result = 'odd'
return result
Made with SlashPage