https://codeforces.com/contest/1562/problem/B
시간 1초, 메모리 256MB
input :
output :
조건 :
n에는 0이 포함되어 있지 않다.
n에서 수들을 최대한 많이 제거한 후에 얻은 수가 소수가 아닐 수 있는가
소수가 아니라는 의미는 합성수 또는 1을 나타낸다.
가장 처음 들었던 생각은 4, 6, 8, 9, 1이 있으면 그냥 얘네를 출력하면 되겠다 였다.
일단 1이 포함된다는 것 자체를 너무 늦게 안 것도 좀 문제가 있었다.
이 5가지 조건을 만족시키는 if를 만들려고 했으니 아주 문제가 있었다.
지금와서 보니 리스트에 이 값들을 넣은 다음에 존재하는지를 확인하는 것이 매우 편하다.
1의 길이는 해결이 가능하고 그럼 2의 길이로 넘어가자.
사실 문제를 푸는 당시에는 모든 길이를 다 따져야 하나? 하는 생각에 문제를 놓고 싶었다.
지금 와서 천천히 다시 보니 따져야 하는 숫자는 매우 적다. 2, 3, 5, 7이 4개의 숫자를 이용해서 만든 수들인데 얘네가 소수이려면 자기자신이 또 나오는 일은 없어야 한다.
22, 33, 과 같은 수는 합성수이기 때문이다.
2의 길이까지는 소수가 발생할 수 있는데 3의 길이에서는 발생할 수 없다.
235, 237, 257, 325, 327, 357, 523, 527, 537, 723, 725, 735 처럼 죄다 1개를 빼버리면 합성수가 될 수 있기 때문이다.
어차피 2의 길이에서도 만들 수 없다면 3의 길이에서 새로운 2의 길이짜리 정답을 얻을 수 있다.
물론 문제를 푸는 당시에는 그냥 짜증나서 4의 길이까지 조합을 통해 문제를 해결하도록 하였다. 그리고 헛웃음이 나와서 그냥 롤이나 하고 잤다.
그러기에 그냥 2개의 숫자를 가지고 정답을 얻을 수 있다고 봐야하는 것이다.
3짜리를 만들어도 2개로 만든 정답을 얻으니까
import sys, math
def check():
visit = set()
for i in range(len(num)):
now = int(num[i])
if now in visit:
continue
visit.add(now)
for j in range(2, int(math.sqrt(now)) + 1):
if now % j == 0:
return now
for i in range(len(num)):
for j in range(i + 1, len(num)):
now = int(num[i] + num[j])
if now in visit:
continue
visit.add(now)
for k in range(2, int(math.sqrt(now)) + 1):
if now % k == 0:
return now
for _ in range(int(sys.stdin.readline())):
k = int(sys.stdin.readline())
n = sys.stdin.readline().rstrip()
num = []
for item in n:
num.append(item)
if '1' in num:
print(1)
print(1)
continue
ans = check()
print(len(str(ans)))
print(ans)