algospot.com :: 질문과 답변: 소인수 분해 알고리즘

소인수 분해 알고리즘

SinAska

안녕하세요.

아래와 같은 궁금증이 생겨 질문 드립니다.

일반적으로 소인수분해를 위해 에라토스테네스채를 이용하여 구하는데,
N이 10¹² 으로 배열에 값을 저장하기 어려울때는, 어떻게 소인수분해가 가능 할까요?

정리하자면,

N \le 10^{12}
$N \le 10^{12}$
일때,

N = \Pi (p_{i}^{q_{i}})
$N = \Pi (p_{i}^{q_{i}})$
형태로 나타내어 pi와 qi값을 구하고 싶습니다.

도움부탁드립니다.

8년 전

2개의 댓글이 있습니다.

hyunhwan
- 우선 에라토스테네스체가 소인수분해를 위한 일반적인 방법이라고 보긴 어렵지 않을까 싶네요.
- 반복문을 통해서 $2$ 부터 $\sqrt{N}$ 까지 보면 되지 않을까요?
8년 전 link
박선준

N을 소인수 분해하면 sqrt(N)보다 큰 소인수는 많아봐야 한개 아닌가요?
sqrt(N) 10^6 까지만 소수 다 구해서 소인수 분해하고 결과가 1이 아니면
그 수도 소수로 생각하면 되지 않을까 싶네요
sqrt(N)보다 큰 소인수가 2개 이상이라면 소인수들의 곱이 N을 초과 할것 같아여

8년 전 link
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.