[BOJ]5636. 소수 부분 문자열

문제

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

 

사용 알고리즘

Brute Force, 에라토스테네스의 체

 

풀이

고려사항

1. 가장 큰 소수인지

2. 2 <= 소수 <= 100,000에 해당되는 소수인지

 

후기

두 방법을 사용하여 prime 함수를 정의하였다.

 

1. Brute Force

2부터 주어진 수까지 나누어 중간에 나머지가 0이 될 수 있는지 여부를 확인하였다.

 

2. 예전 소수 리스트 기록

문제 한 번에 1,000개까지 여러 테스트케이스가 존재할 수 있다.

때문에 예전 소수들을 저장하는 방식을 구현하였다.

prime_lst라는 리스트를 만들고 소수 여부를 확인하여

' 0은 아직 확인하지 않은 숫자, 1은 소수, 2는 소수가 아닌 수 '로 분류하여 관리하였다.

시간이 줄어들 줄 알았지만, 오히려 메모리가 약간 늘어나고 시간은 줄어들지 않았다.

테스트 케이스와 숫자가 크지 않고, 오히려 조건만 많아 이러한 결과가 나온 것 같다.

 

 

코드

import sys

input = sys.stdin.readline

# 방법 1.
# 31120KB, 36ms

# def prime(temp):
#     for i in range(2, temp):
#         if temp % i == 0:
#             return False
#     return True


# 방법 2.
# 32684KB, 36ms

prime_lst = [1, 1] + ([0] * (100000))


def prime(temp):
    if prime_lst[temp] == 1:
        return True
        
    for i in range(2, int(temp**0.5) + 1):
        if prime_lst[i] == 0:
            prime_lst[i] = 1
            for j in range(i * 2, 100000, i):
                prime_lst[j] = 2
    if prime_lst[temp] != 2:
        return True
    else:
        return False


while True:
    origin = input().rstrip()

    if origin == "0":
        break
    else:
        answer = 0
        for i in range(len(origin)):
            for j in range(i + 1, len(origin) + 1):
                temp = origin[i:j]

                if len(temp) < 6 and prime(int(temp)):
                    answer = max(answer, int(temp))
    print(answer)

 

결과