백준 1313번 : 합성소수 (Python)

문제링크

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

문제 총평

- 알고보면 쉬운 완전탐색

문제 접근방식

- n이 천만까지 나오기 때문에 에라토스 테네스의 체를 사용하여 소수를 천만까지 구하고 미리 모든 합성소수를 구해줍니다.

- 이후 각각의 n에 따라서 이분탐색을 통해 미리 구해놓은 합성소수에서 n보다 작거나 같은 합성소수 중 가장 큰수를 출력하면 끝입니다.

- 하지만 맞힌 사람들 코드를 보니 합성소수는 31373 까지 밖에 없다는 걸 깨닷고 소수도 31373까지만 구해주었습니다.

가능한 모든 합성소수

[111, 117, 119, 171, 231, 237, 297, 319, 371, 411, 413, 417, 437, 471, 473, 531, 537, 597, 611, 671, 679, 711, 713, 717, 731, 737, 831, 837, 897, 973, 979, 1131, 1137, 1311, 1313, 1317, 1379, 1797, 1971, 3113, 3131, 3173, 3179, 4197, 4311, 4313, 4317, 4797, 6137, 6179, 7197, 7971, 31373]

정답코드 (천만까지 완전탐색)

import sys; I = sys.stdin.readline
import bisect
prime = [False, False] + [True] * 10000000
ans = []
def find_ans(x):
    t = str(x)
    tt = t[1:]
    if '2' in tt or '4' in tt or '6' in tt or '8' in tt or '0' in tt or '5' in tt:
        return False
    for i in range(2,len(t)):
        for j in range(len(t) - i + 1):
            if not prime[int(t[j:j+i])]:
                return False
    return True
for i in range(2, 10000001):
    if prime[i]:
        for j in range(i * 2, 10000001, i):
            prime[j] = False
for i in range(100,10000001):
    if not prime[i] and i%2 and find_ans(i):
        ans.append(i)
for _ in range(int(I())):
    n = int(I())
    a = bisect.bisect_right(ans, n)-1
    if a == -1:
        print(-1)
    else:
        print(ans[a])

정답코드 (31373까지 완전탐색)

import sys; I = sys.stdin.readline
import bisect
prime = [False, False] + [True] * 31374
ans = []
def find_ans(x):
    t = str(x)
    tt = t[1:]
    if '2' in tt or '4' in tt or '6' in tt or '8' in tt or '0' in tt or '5' in tt:
        return False
    for i in range(2,len(t)):
        for j in range(len(t) - i + 1):
            if not prime[int(t[j:j+i])]:
                return False
    return True
for i in range(2, 31376):
    if prime[i]:
        for j in range(i * 2, 31376, i):
            prime[j] = False
for i in range(100,31376):
    if not prime[i] and i%2 and find_ans(i):
        ans.append(i)
for _ in range(int(I())):
    n = int(I())
    a = bisect.bisect_right(ans, n)-1
    if a == -1:
        print(-1)
    else:
        print(ans[a])

문제 풀이 후 생각

- 완전탐색을 해보고 경우의 수를 확인하는 것도 필요할거 같습니다...

 

 

모르는게 있다면 댓글 또는 godzz733@naver.com으로 메일 남겨 주세요