24503번 - blobfearful
현재 이 문제 파이썬 정답자 모두 폴라드 로 알고리즘으로 인수분해를 진행했습니다.
그리고 39806378 번 제출(http://boj.kr/cb9c2cdcbe5d4c7e...)로 실험해본 결과 에라토스테네스의 체로 단순히 sqrt K까지 소수 배열을 채우기만 해도 TLE가 나옵니다.
이 문제 레이팅이 플래4이고, C++풀이들을 보면 밀러라빈이라던지 폴라드 로 같은 알고리즘은 쓸 필요가 없는 거 같은데 검토해주시면 감사하겠습니다.
에라토스테네스의 체와 밀러 라빈, 폴라드 로 등을 사용하지 않는 풀이가 있습니다.
답변 감사드립니다. 제 체 코드가 https://www.geeksforgeeks.org/... 여기서 가져온 것이었는데 이런 사이트도 "빠른" 코드는 아니었군요...
댓글을 작성하려면 로그인해야 합니다.
drash99 4년 전
현재 이 문제 파이썬 정답자 모두 폴라드 로 알고리즘으로 인수분해를 진행했습니다.
그리고 39806378 번 제출(http://boj.kr/cb9c2cdcbe5d4c7e...)로 실험해본 결과 에라토스테네스의 체로 단순히 sqrt K까지 소수 배열을 채우기만 해도 TLE가 나옵니다.
이 문제 레이팅이 플래4이고, C++풀이들을 보면 밀러라빈이라던지 폴라드 로 같은 알고리즘은 쓸 필요가 없는 거 같은데 검토해주시면 감사하겠습니다.