[BOJ 백준] 1747번 : 소수&팰린드롬(Python, 파이썬)

www.acmicpc.net/problem/1747

1747번: 소수&팰린드롬

 

소수 판별과 팰린드롬을 사용하는 문제이다. 파이썬의 경우 팰린드롬은 굉장히 쉽게 판별할 수 있으므로 패스한다.

 

소수 판별은

• 에라토스테네스의 체
• 2부터 제곱근까지 나머지 확인

2가지 방식으로 테스트를 해봤는데, 시간복잡도는 크게 차이나지 않는 것 같다.

 

다만, 소수의 갯수보다 팰린드롬의 갯수가 더 많으므로 팰린드롬인지 확인해주는 것을 먼저 해주는게 시간복잡도 측면에서 효율적이다.

 

 

아래 사진의 순서대로 사용한 알고리즘 및 판별 순서이다

• 에라토스테네스의 체 사용 (228ms)
  • 팰린드롬 확인 -> 소수 확인
• 제곱근까지 나누기(956ms)
  • 팰린드롬 확인 -> 소수 확인
• 제곱근까지 나누기(196ms)
  • 소수확인 -> 팰린드롬 확인

알고리즘 별 소요시간

 

 

 

소스 코드

 

import sys, math

#에라토스테네스의 체
prime = [True]*(1005000) 
prime[1] = False # 1은 소수가 아님
m = int(math.sqrt(1005000))
for i in range(2, m+1):
    if prime[i] == True:
        for j in range(i+i, 1005000, i):
            prime[j] = False  

# 소수 판별 알고리즘 : 제곱근까지 구하기
def isPrime(x):
    if x == 1: # 1은 소수가 아님
        return False
    for i in range(2, int(math.sqrt(x))+1):
        if x % i == 0:
            return False
    return True
    
    
def isPalindrome(x):
    x = str(x)
    tmp = x[::-1]
    if x == tmp:
        return True
    else:
        return False

n = int(input())
while True:
    if isPalindrome(n):
        if isPrime(n):
            print(n)
            exit(0)
    n += 1