목록약수의 개수 (1)

Dawn

[파이썬] 약수의 개수 구하기, 그런데 최적화를 곁들인

가장 기본적인 약수의 개수를 구하는 문제부터 시작해보자. 어떤 자연수 n이 주어졌을 때, n의 약수의 개수를 구하라.약수는 나누어 떨어지게 하는 수를 의미한다.n = int(input())cnt = 0for i in range(1, n+1): if n % i == 0: cnt += 1 print(cnt)어떤 수를 입력 받고, 개수를 셀 변수를 선언한다.range는 end에서 -1한 값까지 반복한다.자기자신을 나누는 것도 가능하기에 n+1을 하여 구해준다. 시간복잡도는 n에 따라 반복횟수가 선형적으로 증가하기에 O(n) 이다. (1부터 n까지 반복) 이제 최적화를 해보자.약수는 항상 a * b = n 쌍으로 존재하기 때문에 짝수 개가 된다.ex) 6 = 1 * 6, 2 * 3..
알고리즘 2024. 12. 5. 00:46
이전 Prev 1 Next 다음