1990번 - 소수인팰린드롬
처음에는 에라토스테네스의 체를 통해 먼저 소수만 걸러낸 후, 팰린드롬 수인지 아닌지 판정을 했는데 메모리 초과가 생겨서 다른 방법을 찾아봤습니다.
어떤 분께서 팰린드롬 수를 먼저 판정한 후, 소수 판정을 하라고 하셔서 바꿔보았습니다만..시간초과가 계속 뜨네요.
어떤 부분을 개선하면 나아질까요? 분해서 잠을 못 자겠습니다..도와주세요..
최적화가 하나 더 필요합니다. 팰린드롬 수의 길이가 짝수인 경우 25377352와 같다면 11, 1001, 100001 등이 모두 11의 배수이기 때문에 11 하나를 제외하고는 짝수 길이 팰린드롬은 소수가 될 수 없습니다. 이 최적화를 하면 b의 범위가 최대 10,000,000으로 제한되는 것과 같게 되므로 수행시간이 1/10 정도로 감소합니다.
제시해주신 아이디어를 생각해내는게 아직은 꽤나 힘드네요. 좋은 해결책을 주셔서 감사합니다!
c++에서는 bitset을 사용하면 1억개의 에라체를 쓸수있긴 합니다.. 파이썬은 모르겠네요
댓글을 작성하려면 로그인해야 합니다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
한국어 | English (Beta)
AltStyle によって変換されたページ (->オリジナル) / アドレス: モード: デフォルト 音声ブラウザ ルビ付き 配色反転 文字拡大 モバイル
sunday073 4년 전 0
처음에는 에라토스테네스의 체를 통해 먼저 소수만 걸러낸 후, 팰린드롬 수인지 아닌지 판정을 했는데 메모리 초과가 생겨서 다른 방법을 찾아봤습니다.
어떤 분께서 팰린드롬 수를 먼저 판정한 후, 소수 판정을 하라고 하셔서 바꿔보았습니다만..시간초과가 계속 뜨네요.
어떤 부분을 개선하면 나아질까요? 분해서 잠을 못 자겠습니다..도와주세요..