백준 1747 파이썬 에라토스테네스의 체를 이용 팰린드롬

백준 1747 - 소수&팰린드롬

문제

https://www.acmicpc.net/problem/1747

1747번: 소수&팰린드롬

1747번

답안 코드 :

import math

N = int(input())

A = [0] * (10000001)

for i in range(2, len(A)):

    A[i] = i

for i in range(2, int(math.sqrt(len(A)) + 1)):  # 제곱근까지만 수행

    if A[i] == 0:

        continue

    for j in range(i + i, len(A), i):  # 배수 지우기

        A[j] = 0

def isPalindrome(target):  # 펠린드롬 수 판별 함수

    temp = list(str(target))

    s = 0

    e = len(temp) - 1

    while (s < e):

        if temp[s] != temp[e]:

            return False

        s += 1

        e -= 1

    return True

i = N

while True:  # N부터 1씩 증가시키면서 소수와 팰림드롬 수가 맞는지 판별

    if A[i] != 0:

        result = A[i]

        if (isPalindrome(result)):

            print(result)

            break

    i += 1

생각 :

# 문제 분석
# 에라토스테네스의 체를 이용해 범위에 해당하는 모든 소수 구하기
# 구한 소수 중 팰린드롬 수를 찾기

# 팰린드롬 수를 판별할 때 숫잣값이 리스트 형태로 적절하게 변환이 가능하다.
# 위를 알면 더 쉽게 로직 구현 가능

# 문제 풀이
# 2 ~ 10,000,000 사이에 존재하는 모든 소수 구하기
# 그리고 나서 펠린드롬 수 구해야함

# 소수의 값을 리스트 형태로 변환하고 
# 양 끝의 투 포인터를 비교하면 쉽게 펠린드롬 수 구할 수 있음

 

정수론 정리 글들

 

https://mkisos.tistory.com/entry/%EC%A0%95%EC%88%98%EB%A1%A0-%EC%86%8C%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0-%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B1%84

정수론 : 소수 구하기 에라토스테네스의 채

 

https://mkisos.tistory.com/entry/%EC%A0%95%EC%88%98%EB%A1%A0-%EC%98%A4%EC%9D%BC%EB%9F%AC-%ED%94%BC

정수론 : 오일러 피

https://mkisos.tistory.com/entry/%EC%A0%95%EC%88%98%EB%A1%A0-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95

정수론 : 유클리드 호제법

https://mkisos.tistory.com/entry/%EC%A0%95%EC%88%98%EB%A1%A0-%ED%99%95%EC%9E%A5-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%A0%9C%EB%B2%95

정수론 : 확장 유클리드 호제법