039 소수＆팰린드롬

첫번째 코드

 

소수를 구하는 코드는 이전 문제에서부터 열심히 작성해봤다.

그래서 소수를 구성하는 코드는 머리를 조금 쓰면 금방 작성했는데...

거꾸로해도 똑같은!! 이 부분이 문제여서 책을 참고했다.

근데 그냥 인덱스를 통해서 같은지 같지 않은지 판별하는 함수를 따로 만들어 이용했다.

 

import sys
import math
input = sys.stdin.readline

n = int(input())
max_num = 1000000

A = list(range(max_num + 1))
A[1] = 0

for i in range(int(math.sqrt(max_num)) + 1):
    if A[i] == 0:
        continue
    else:
        for j in range(i * i, max_num + 1, i):
            A[j] = 0

def Pelindrome(x):
    data = list(str(x))
    index1 = 0
    index2 = len(data) - 1
    
    while (index1 < index2):
        if data[index1] != data[index2]:
            return False
        index1 += 1
        index2 -= 1
        
    return True

N = n

while True:
    if A[N] != 0:
        if Pelindrome(A[N]):
            print(A[N])
            break
    N += 1

 

근데 왜 백준에서는 IndexError가 나오는 것일꺄...

---

두번째 코드

 

스터디에 물어봤다!!

그랬더니 천사분이 친절하게 대답해주셨다 ㅠㅠ(감사합니다ㅠㅠ)

 

max_num을 키우셔야 될거에용

n으로 100만 입력했을 때 답이 나와야 하니 max_num을 한 150만까지 키워보시고 100만 입력해서 나오는지 확인해보시면 좋을것 같아요!!

 

해서 확인할 결과 1003001로 값이 나왔다! 그리고 백준으로도 통과가 되었다! 근데 왜지...

 

n보다 크거나 같고 소수면서 팰린드롬인 수를 찾는건데 그 정답 값이 100만 이하라는 얘기는 없으니 100만을 입력했을 때는 그보다 큰 값이 답인게 맞는것 같아요 :) 까지 설명해주시는 친절한 천사분 ㅠㅠㅠ

 

그리고 꿀팁까지 알려주셨다!!

 

에라토스테네스의 체 구현하실 때 for j in range(i + i, max_num + 1, i)
부분을 for j in range(i * i, max_num + 1, i) 처럼 구현해주셔야 충분히 빨라요

 

7의 배수 처리하는 상황이라면 7 * 2, 7 * 3, 7 * 4, 7 * 5, 7 * 6, 7 * 7, … 을 지우는건데,

7 * 2는 2의 배수, 7 * 3은 3의 배수, … 7 * 6은 6의 배수라서 이미 지워졌다는게 확실하니 지금 턴에는 안지워도 되거든요

 

import sys
import math
input = sys.stdin.readline

n = int(input())
# max_num = 1000000
max_num = 1500000

A = list(range(max_num + 1))
A[1] = 0

for i in range(int(math.sqrt(max_num)) + 1):
    if A[i] == 0:
        continue
    else:
        for j in range(i * i, max_num + 1, i):
            A[j] = 0

def Pelindrome(x):
    data = list(str(x))
    index1 = 0
    index2 = len(data) - 1
    
    while (index1 < index2):
        if data[index1] != data[index2]:
            return False
        index1 += 1
        index2 -= 1
        
    return True

N = n

while True:
    if A[N] != 0:
        if Pelindrome(A[N]):
            print(A[N])
            break
    N += 1

 

통과! 천사님 만세 ㅠㅠㅠ

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Silver/1747.%E2%80%85%EC%86%8C%EC%88%98%EF%BC%86%ED%8C%B0%EB%A6%B0%EB%93%9C%EB%A1%AC

programmers/백준/Silver/1747. 소수＆팰린드롬 at main · ornni/programmers