cheetose   6년 전

이 문제를 풀기 위해서 인터넷 여기저기 정말 열심히 돌아다녔는데 O(N^1/2)보다 빠른 알고리즘을 찾지 못했습니다. (11689번 문제를 풀고 큐브러버님의 코드를 봐서 약간의 최적화하는 방법을 배웠습니다.)

여기서 두 가지로 갈리는데

  1. 이보다 더 빠른 알고리즘이 있다면, 어떤 알고리즘을 공부해야하는지
  2. 만약 그게 아니라면, 주어진 입력 범위 내의 가장 큰 소수는 999999999999999989 입니다. Ideone 기준으로 2.7초 정도 걸리는데 문제 푼 사람들의 실행속도가 비정상적으로 빠른 것 같습니다.

만약 다른 알고리즘이 있다면 2번은 무시해주세요.

아무튼 이 문제의 접근 방법을 알고 싶습니다.

kipa00   6년 전

풀지 않아서 확실한 답변은 못 드립니다만, Pollard rho algorithm일걸요?

ntopia   6년 전

저도 폴라드 로 썼어요

doju   6년 전

@bessapple14 문제를 착각하신 것 아닌가요? 이 문제는 11689번보다 제한이 더 큰 다른 문제입니다.

cheetose   6년 전

역시 다른 알고리즘이었군요 ㅠㅠ 

새롭게 공부할 게 생겼네요 감사합니당

cheetose   6년 전

맞았습니다 감사합니다!

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