5356 소수 부분 문자열 _python

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

5636번: 소수 부분 문자열

소수? 부분 문자열?

 

 

 

 

문제 접근

소수? 에라토스테네스의 체

부분 문자열? [:]

에라토스테네스의 체로 미리 소수를 판별하고, while문을 반복하는 동안 부분문자열을 체크하면 된다.

부분문자열은 최대값을 찾아야 하기 때문에 1부터 순서대로 찾는다면 최대값을 찾을 수 있다.

시간을 조금 더 단축할 방법이 있지않을까 하다가 5자리부터 1자리까지 줄여나가며 탐색을 하고,

각 자리수에서 찾는다면 더 작은 자리수는 찾지않도록 만들었다.

물론 효과는 미미했다.

 

 

 

 

풀이

 

from collections import deque
import sys
input = sys.stdin.readline

"""
5636
에라토스테네스의 체로 소수 10만까지 찾아둠
소수 최대길이(5숫자)부터 1자리수까지 줄여나가며 탐색
"""

primeNum = [False]*2 + [True]*(99999)
for i in range(2,int(100000**0.5)+1):
    for j in range(i*2, 100001, i):
        primeNum[j] = False

while True:
    ans = 0
    x = input()
    if x=="0\n":
        break
    for i in range(5,0,-1):
        if len(x)>i and ans==0:
            for j in range(0,len(x)-i):
                num = int(x[j:j+i])
                if primeNum[num]:
                    ans = max(num, ans)
    
    print(ans)

136ms