https://www.acmicpc.net/problem/1990
1990번: 소수인팰린드롬151은 소수이면서 동시에 팰린드롬이기 때문에 소수인 팰린드롬이다. 팰린드롬이란 앞으로 읽어나 뒤로 읽으나 같은 수를 말한다. 예를 들어 1234는 앞으로 읽으면 1234지만, 뒤로 읽으면 4321이 되www.acmicpc.net
진짜 씨발 ㅈ같은 문제였다.
처음에는 ‘골드치고 웰케 쉽지’ 했는데 역시나 함정이 숨어있었다.
가장 먼저, 체로 풀었는데 시간초과가 났다.
그래서 a부터 b까지의 모든 펠린드롬을 n 구하고, 이를 int(n**0.5)+1 까지의 모든 수로 나눠서 판별했다.
역시 시간초과가 났다.
여기서부터 별짓을 다해봤다.
짝수중에 소수는 2밖에 없으므로, 2로 먼져 나눠보고 3부터 2씩 증가시켜서 나눠보고,
함수형으로도 명령형으로도 해보고
뭔짓을해도 시간초과가나서 인터넷에 답을 찾아봤더니
11의 배수 판정법은 홀수자리 숫자의합-짝수자리 숫자의 합이 11의 배수면 된단다.
그래서 모든 길이가 짝수인 펠린드롭은 11의 배수란다.
즉 최대길이가 100,000,000인데, 10,000,000을 넘는 펠린드롭 수는 없다.
최대 펠린드롭수
진짜 어? 이거 개쉬운데 하고 하나만 풀고 잘려했는데
억울해서 잠을 설쳤다.
코드
def sosu(x): if x%2==0:return for ii in range(3,int(x**0.5)+2):
if x%ii==0: return print(x)
a,b=map(int,input().split())if b>9999997: b=9999997 for i in range(a,b+1):
if str(i)==str(i)[::-1]: sosu(i)print(-1)