[알고리즘] 백준 5636 파이썬 - 소수 부분 문자열

 

5636번: 소수 부분 문자열

문제

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

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

 

문제풀이

#01
n=100000
tmp=[False,False]+([True]*(n-1))
for i in range(2,int(n**0.5)+1):
    if tmp[i]:
        for j in range(2*i,n+1,i):
            tmp[j]=False
    prime=[i for i in range(2,n+1) if tmp[i]]
#02
while True:
    n=input()
    if n=="0":
        break
    ans=2
    #03
    for i in prime:
        if str(i) in n:
            ans=i
    print(ans)

- #01  :에라토스테네스의 체를 이용하여서 100000까지의 소수를 prime에 저장한다.

- #02 : n을 문자로 입력받고, 만약 "0"이면 while문을 종료한다. ans의 기본값은 2로 설정한다.

- #03 : i에 prime 즉 소수값을 하나씩 넣어서 str로 표현한 값이 입력받은 n 문자열에 존재한다면

           ans에 i를 저장한다. i는 점차 큰 소수가 들어오기에 저장하는 순서는 관계가 없다.

           2~100000까지의 소수의 개수가 그렇게 크지 않기 때문에 시간 초과가 일어나지 않는다.