비밀번호 486 문제에서 다루는 약수의 개수를 구하는 알고리즘에 대해서 질문드립니다 tennie 책의 알고리즘은 n의 가장 작은 소인수가 p이고 이 소인수가 a번 출현한다면 factor(n)은factor(n/p)*((a+1)/a)이라고 되어있는데 여기서 (a+1)/a 은 어떻게 나온 식인가요?? 곰곰히 생각해봐도 안떠올라서 질문드립니다. 6년 전
2개의 댓글이 있습니다. astein n = p^a인 자연수라고 가정했을 때, factor(n)은 p^0, p^1, ..., p^a 로 총 a+1개가 존재하기 때문입니다. n = p^a * n' 인 경우에도 비슷하게 접근할 수 있습니다. 6년 전 link tennie 답변주셔서 감사드립니다^^ 6년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
tennie
책의 알고리즘은 n의 가장 작은 소인수가 p이고 이 소인수가 a번 출현한다면 factor(n)은factor(n/p)*((a+1)/a)이라고 되어있는데 여기서 (a+1)/a 은 어떻게 나온 식인가요?? 곰곰히 생각해봐도 안떠올라서 질문드립니다.
6년 전