2014년 7월 31일 목요일

2312 - 수 복원하기

소수 찾기처럼 에라토스테네스의 체를 이용하면 굳이 n까지 확인을 안 해도 될거라 생각했는데, 아닌가보다.

매개변수를 2부터 N까지 증가시키면서 나누어 떨어진다면 N을 2로 나눌 수 있는 만큼 나누고 몇번 나눴는가를 출력했다.

사실 매개변수를 k 라고 한다면 logkN 으로 알 수 있지 않을까 했는데 그렇지도 않았다. 나누어떨어진다는 이유로 다른 소인수를 무시하고 억지로 나누어버리기 때문. (예를들면 k=2 인 상황에서 n=10)
댓글 쓰기

게시글 목록