소인수 분해와 약수
N을 소수 거듭제곱으로 분해하고 약수 개수를 셉니다
소인수 분해와 약수은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
N 분해하기
1보다 큰 모든 정수는 소수들의 유일한 곱으로 나타낼 수 있습니다. 이 분해, 즉 소인수분해를 구하면 많은 정수론 문제를 해결할 수 있습니다. 🧩
시행 나눗셈의 아이디어
n을 나누는 가장 작은 소수를 꺼내고, 그 소수로 나눈 뒤 반복합니다. 이 간단한 시행 나눗셈은 n을 1까지 줄여 갑니다.
제곱근까지 반복하기
i*i가 n 이하인 동안 약수 i를 테스트합니다. 제곱근을 지나면 남을 수 있는 소인수는 최대 하나입니다.
while i * i <= n:
...각 인수 추출하기
i가 n을 나누는 동안 계속 나누고 i를 기록합니다. 이렇게 하면 다음으로 넘어가기 전에 해당 소수의 전체 지수를 얻을 수 있습니다.
while n % i == 0:
factors.append(i)
n //= i남은 소수
반복문이 끝난 뒤에도 n이 1보다 크다면 n 자체가 제곱근보다 큰 소수 인수입니다. 이를 한 번 추가합니다.
if n > 1:
factors.append(n)전체 과정
이 과정을 합치면 O(sqrt n) 시간에 소인수분해를 수행하며, 각 소수를 전체 중복 횟수와 함께 순서대로 반환합니다.
def factorize(n):
f, i = [], 2
while i * i <= n:
while n % i == 0:
f.append(i); n //= i
i += 1
if n > 1: f.append(n)
return f지수별로 묶기
약수의 개수를 세려면 2,2,2가 아니라 2^3처럼 각 소수와 그 지수가 필요합니다. 카운터를 사용하면 반복되는 값을 깔끔하게 셀 수 있습니다.
from collections import Counter
exp = Counter(factorize(n))약수 공식
n이 p1^a 곱하기 p2^b라면 약수의 개수는 (a+1) 곱하기 (b+1)입니다. 각 지수마다 하나의 선택지가 추가됩니다.
약수 개수 세기
모든 소수의 각 지수에 1을 더한 뒤 서로 곱하세요. 그러면 약수를 일일이 나열하지 않고도 전체 약수 개수를 구할 수 있습니다.
count = 1
for e in exp.values():
count *= (e + 1)약수의 합
관련 공식에서는 각 소수의 등비급수를 사용해 약수의 합을 구합니다. 이 공식을 알면 완전수와 아리코트 수 문제를 해결하는 데 도움이 됩니다.
체로 속도 높이기
많은 수를 소인수분해해야 한다면 체를 사용해 각 수의 가장 작은 소인수를 미리 계산하세요. 그러면 각 질의의 소인수분해를 로그 n 단계 만에 수행할 수 있습니다.
빠른 확인
구체적인 수에 약수 개수 공식을 적용해 보세요.
요약
이제 trial division으로 O(sqrt n) 시간에 N을 소인수분해하고, 남은 소수를 처리하고, 지수별로 묶은 다음 곱셈 공식을 사용해 약수 개수를 셀 수 있습니다. ✅
자주 묻는 질문
“소인수 분해와 약수” 강의는 무료인가요?
네 — “소인수 분해와 약수” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“소인수 분해와 약수”에서 뭘 배우나요?
N을 소수 거듭제곱으로 분해하고 약수 개수를 셉니다 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.
“소인수 분해와 약수” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.