[BaekJoon] 1990번 : 소수인팰린드롬 (Python)

코딩 1일 1문제! 오늘의 문제는 백준의 소수인팰린드롬 입니다.

1990번: 소수인팰린드롬

첫번째 시도!

def get_primary_num_eratos(N):
    nums = [True] * (N)
    
    for i in range(2, len(nums) // 2 + 1):
        if nums[i] == True:
            for j in range(i+i, N, i):
                nums[j] = False
    return [i for i in range(2, N) if nums[i] == True]

def check_is_palindrome(num):
    is_palindrome = False
    num = str(num)
    if num == num[::-1]:
        is_palindrome = True
    return is_palindrome

def solution(A, B):
    primary_nums = [num for num in get_primary_num_eratos(B + 1) if A <= num <= B and check_is_palindrome(num)]
    for num in primary_nums:
        print(num)
    print("-1")
    
if __name__ == "__main__":
    A, B = map(int, input().split())
    
    solution(A, B)

먼저 첫번째 시도로는 에라스토테네스의 체 방법을 활용해 입력받은 두 수 A와 B 사이의 소수를 모두 구한 다음

팰린드롬인 수만 찾아 남기기로 했습니다.

호기롭게 제출하였으나 메모리 초과라는 결과가 나왔습니다.

두번째 시도!

def check_is_primary_num(num):
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

def check_is_palindrome(num):
    is_palindrome = False
    num = str(num)
    if num == num[::-1]:
        is_palindrome = True
    return is_palindrome

def solution(A, B):
    palindrome_numbers = [num for num in range(A, B + 1) if check_is_palindrome(num)]
    primary_nums = [num for num in palindrome_numbers if check_is_primary_num(num)]
    for num in primary_nums:
        print(num)
    print("-1")
    
if __name__ == "__main__":
    A, B = map(int, input().split())
    
    solution(A, B)

이번엔 반대로 입력받은 두 수 A, B 사이의 팰린드롬 수를 먼저 찾고나서 소수인 숫자를 찾아보았습니다.

결과는! 메모리초과는 피했으나! 시간초과 득템!

세번째 시도!

def check_is_primary_num(num):
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

def check_is_palindrome(num):
    is_palindrome = False
    num = str(num)
    if num == num[::-1]:
        is_palindrome = True
    return is_palindrome

def solution(A, B):
    if B > 10000000:
        B = 10000000
    palindrome_numbers = [num for num in range(A, B + 1) if check_is_palindrome(num)]
    primary_nums = [num for num in palindrome_numbers if check_is_primary_num(num)]
    for num in primary_nums:
        print(num)
    print("-1")
    
if __name__ == "__main__":
    A, B = map(int, input().split())
    
    solution(A, B)

마지막으로 10,000,000 보다 큰 숫자에서는 팰린드롬인 소수가 없다는 것을 알고

B가 10,000,000보다 클때 B를 10,000,000으로 바꾼다음에 실행하니 해결되었습니다.

SOMJANG/CODINGTEST_PRACTICE