#15. Algorithm11_python) 약수 구하기

문제) 약수 구하기

정수를 입력받아, 약수를 구해 출력

 

---

 

step1) 테스트1 : 기본   # n = 36

n = 36

for i in range(1, n+1):       # 1~n까지 약수인지 확인
    if n % i == 0:            # 약수면
        print(i, end = ' ')   # 출력

print()

>>>
1 2 3 4 6 9 12 18 36

 

step2) 테스트2 : 리스트에 담기   # n = 36

# 확장 : list에 정답 담아서 출력, n = 36가정

n = 36

list_answer = []               # 약수를 담을 빈 리스트 생성

for i in range(1, n+1):        # 1~n까지 약수인지 확인
    if n % i == 0:             # 약수면
        list_answer.append(i)  # 리스트에 추가

print(list_answer)

>>>
[1, 2, 3, 4, 6, 9, 12, 18, 36]

 

step3) 메서드

def algo11(n):
    list_answer = []               # 약수를 담을 빈 리스트 생성

    for i in range(1, n+1):        # 1~n까지 약수인지 확인
        if n % i == 0:             # 약수면
            list_answer.append(i)  # 리스트에 추가
    return list_answer             # 정답 리스트 리턴

n = int(input('숫자 입력 : '))
print(f'{n}의 약수 : {algo11(n)}')

>>>
숫자 입력 : 72
72의 약수 : [1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72]

---

# 배운 점

• 리스트를 활용한 정답 출력

# 소회

• 구글링 해보니, '임의의 자연수 N의 약수들 중에서 두 약수의 곱이 N이 되는 약수 A와 B는 반드시 존재한다'는 성질을 활용하여 효율적으로 문제 푸는 방식이 있음 -> 고민해 보기
• 그런데, 애초에 이런 수학적 성질을 모르면 알고리즘을 짤 수 없을 듯