kesakiyo   2년 전

생각하다 암걸릴거 같아서 질문을 올립니다...

4149번 큰 수 소인수 분해 문제인데 일반적으로 사용하는 소인수 분해 알고리즘으로는

19자리의 정수를 소인수 분해 하는데는 큰 무리가 있습니다.

그래서 여러 방면으로 알아본 결과 '타원 곡선 알고리즘', '폴라드 로 알고리즘', '이차 체 알고리즘', '넘버 필드 체 알고리즘' 등등

정말 다양한 알고리즘들이 있더라구요......정수론의 지식이 전무한지라 이중에 어떠한 알고리즘을 사용해야 하는지 도저히 감이

안잡히네요.

이 문제를 어떻게 접근해야 하는지 조그마한 힌트좀 주실 수 있으신가요??

염치 불구하고 질문을 해 봅니다ㅜㅜ

WeissBlume   2년 전

제 경우는 Pollard Rho(+Miller-Rabin Primality Test)만 써서 통과했습니다ㅎㅎ

pichulia   2년 전

저도 폴라로우 써서 풀었습니다.ㅎㅎ

아 그리고 폴라로우로 짰다면 

1219  이 숫자가 23 * 53 으로 인수분해가 잘 되는지 꼭 테스트하시길...조그마한 팁입니다.

pl0892029   2년 전

Pollard Rho를 보신다면 여기 사이트 강추합니다. ^-^
http://www.cs.colorado.edu/~srirams/classes/doku.p...

댓글을 작성하려면 로그인해야 합니다.