사용자 도구

사이트 도구


ps:problems:boj:1990

소수인팰린드롬

ps
링크acmicpc.net/…
출처BOJ
문제 번호1990
문제명소수인팰린드롬
레벨골드 5
분류

정수론

시간복잡도O(sqrt(n) * logn)
인풋사이즈n<=10^8
사용한 언어Python 3.11
제출기록33376KB / 64ms
최고기록36ms
해결날짜2023/03/31

풀이

  • 기본적으로는 Palindromic Primes과 같은 문제이다. 차이점은, 갯수만 출력하느냐 모든 소수를 하나씩 다 출력하느냐와 범위의 차이.
  • Palindromic Primes에서 설명했듯이, 회문수를 먼저 만들고서 각각에 소수 테스트를 하는 것이 가장 빠른 방법이지만, 범위가 작기때문에 소수 목록을 먼저 만들고서 각각에 대해서 회문 테스트를 하는 방법도 통과한다.
    • 시간은 64ms vs 464ms 로 많이 느려졌지만 코드는 더 심플하다.
  • 그냥 10^8 이하의 회문소수를 전처리해서 코드에 박아놓는 것도 가능하다! 이렇게 해도 회문소수가 많지 않아서 코드 길이가 6181b밖에 안된다.

코드

코드 1 - 회문수 먼저 만들고 소수 판별

"""Solution code for "BOJ 1990. 소수인팰린드롬".

- Problem link: https://www.acmicpc.net/problem/1990
- Solution link: http://www.teferi.net/ps/problems/boj/1990

Tags: [Number theory]
"""

from teflib import numtheory


def main():
    a, b = [int(x) for x in input().split()]

    for x in (5, 7, 11):
        if a <= x <= b:
            print(x)
    beg = size = 10
    while beg * size <= b:
        for i in range(beg, beg + size):
            s = str(i)
            n = int(s + s[-2::-1])
            if a <= n <= b and numtheory.is_prime(n):
                print(n)
        beg += size * 2
        if beg > size * 10:
            beg = size = size * 10
    print('-1')


if __name__ == '__main__':
    main()

코드 2 - 소수 먼저 만들고 회문수 판별

"""Solution code for "BOJ 1990. 소수인팰린드롬".

- Problem link: https://www.acmicpc.net/problem/1990
- Solution link: http://www.teferi.net/ps/problems/boj/1990

Tags: [Number theory]
"""

from teflib import numtheory

MAX_NUM = 10_000_000


def main():
    a, b = [int(x) for x in input().split()]
    for p in numtheory.prime_list(a, min(b, MAX_NUM)):
        p = str(p)
        if p[::-1] == p:
            print(p)
    print('-1')


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
V O B M W
 
ps/problems/boj/1990.txt · 마지막으로 수정됨: 2023/03/31 08:38 저자 teferi