소인수 분해 알고리즘 SinAska 안녕하세요. 아래와 같은 궁금증이 생겨 질문 드립니다. 일반적으로 소인수분해를 위해 에라토스테네스채를 이용하여 구하는데, N이 \( 10^{12} \)으로 배열에 값을 저장하기 어려울때는, 어떻게 소인수분해가 가능 할까요? 정리하자면, \( N \le 10^{12} \) 일때, \( N = \Pi (p_{i}^{q_{i}}) \) 형태로 나타내어 pi와 qi값을 구하고 싶습니다. 도움부탁드립니다. 10년 전
2개의 댓글이 있습니다. hyunhwan 우선 에라토스테네스체가 소인수분해를 위한 일반적인 방법이라고 보긴 어렵지 않을까 싶네요. 반복문을 통해서 $2$부터 $\sqrt{N}$까지 보면 되지 않을까요? 10년 전 link 박선준 N을 소인수 분해하면 sqrt(N)보다 큰 소인수는 많아봐야 한개 아닌가요? sqrt(N) 106 까지만 소수 다 구해서 소인수 분해하고 결과가 1이 아니면 그 수도 소수로 생각하면 되지 않을까 싶네요 sqrt(N)보다 큰 소인수가 2개 이상이라면 소인수들의 곱이 N을 초과 할것 같아여 10년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
SinAska
안녕하세요.
아래와 같은 궁금증이 생겨 질문 드립니다.
일반적으로 소인수분해를 위해 에라토스테네스채를 이용하여 구하는데,
N이 \( 10^{12} \)으로 배열에 값을 저장하기 어려울때는, 어떻게 소인수분해가 가능 할까요?
정리하자면,
\(
N \le 10^{12}
\)
일때,
\(
N = \Pi (p_{i}^{q_{i}})
\)
형태로 나타내어 pi와 qi값을 구하고 싶습니다.
도움부탁드립니다.
10년 전