글 읽기 - 틀린 것 같은데 어디서 틀렸을까요?ㅠㅠ 도와주세요...

abcyj 2년 전 0

코드의 13~16번 줄이 틀린 것 같은데 왜 틀렸을까요..?

그 부분을

for x in range(n//2,1,-1):
if n-x in p and x in p:
break
print(x,n-x)

로 하면 맞습니다...

제 짧은 생각에는 소수 중에 찾으면 빠를 거라고 생각했는데 전체 수를 다 살펴봐야 맞는 이유가 있나요?

T = int(input())
def prime(n):
    a = [False,False]+[True]*(n-1)
    for i in range(2,int(n**0.5)+1):
        if a[i] == True:
            for j in range(i+i,n+1,i):
                a[j] = False
    return [k for k in range(2,n+1) if a[k] == True]
for t in range(T):
    n = int(input())
    p = prime(n)
    # 틀린 부분!!!!
    for x in p[int(len(p)/2)-1:]:
        if n-x in p:
            break
    print(n-x,x)

evenharder 2년 전 3

문제 조건상 두 소수의 차가 최소가 되는 쌍을 찾아야 하는데, p의 중앙은 n/2이 아니기 때문입니다.

abcyj 2년 전 0

답변 감사합니다! p의 중앙이 n/2이 아니라는 게 무엇을 의미할까요?

제 생각으로는 p[int(len(p)/2)-1:]로 나타낸 것이 p의 반쪽 뒷부분(p의 원소의 개수가 홀수일 경우 가운데 원소 포함)을 돌게 되고 이것이 두 소수의 차가 최소가 되는 쌍을 찾을 것이라고 생각했습니다!

아직 뭔가 제대로 이해가 안되네요ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

틀린 것 같은데 어디서 틀렸을까요?ㅠㅠ 도와주세요...

abcyj 2년 전 0

evenharder 2년 전 3

abcyj 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말