백준 5636번 소수 부분 문자열 파이썬

문제

숫자로 이루어진 문자열이 주어진다. 이때, 부분 문자열 중에서 가장 큰 소수를 찾는 프로그램을 작성하시오.

이 문제에서는 2보다 크거나 같고, 100,000보다 작거나 같은 소수만 소수이다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 1,000개를 넘지 않는다.

각 테스트 케이스는 길이가 255를 넘지 않는 숫자 문자열로 이루어져 있다. 입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 가장 큰 소수 부분 문자열을 출력한다.

예제 입력 1

11245
91321150448
1226406
0

예제 출력 1

11
1321
2

제출답안

import math
import sys
input = sys.stdin.readline
def is_prime_number(x):
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            return False
    return True

num_list = []
for i in range(2,100000+1):
    if is_prime_number(i) == True:
        num_list.append(i)

list_prime = []
k = 1
while True:
    a = list(input().strip())
    max_num = 0
    if sum(list(map(int,a))) == 0:
        break
    number = 1
    while number < len(a):
        b = 0
        for i in range(number,len(a)+1):
            prime = int(''.join(a[b:i]))
            if prime in num_list:
                max_num = max(max_num,prime)
            b +=1
        number +=1
        if prime in num_list:
            max_num = max(max_num, prime)
    if 1 < max_num <= 100000:
        list_prime.append(str(max_num))
print('\n'.join(list_prime))

1. 우선 범위인 2~100,000까지 소수를 다 구한다.
2. 입력받은 문자열을 1개,2개,3개씩 길이만큼 계속 만들어서 소수를 확인한다.
3. 그러면서 max를 비교해서 리스트에 저장한다.
4. 최종적으로 출력하자.