17103

날짜 : 2023. 05. 06

사용 언어 : python

 

문제

 

 

코드

import sys
prime = [True] * 1000001  # 소수면 True, 아니면 False
prime[0], prime[1] = False, False
p = dict()  # 소수 리스트
for i in range(2, int(1000001**0.5)+1):  # 에라토스테네스의 체
    if prime[i]:  # 소수인 경우
        p[i] = True  # 소수 추가
        idx = 2
        while i * idx < 1000001:
            prime[i*idx] = False
            idx += 1
#print(len(prime), len(p))
t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())  # 수 입력
    cnt = 0
    for i in range(2, n//2+1):
        if i > n: break
        if prime[i] and prime[n-i]:
            cnt += 1
    print(cnt)

 

풀이

- 입력받는 수의 최대값이 100만이기 때문에 100만 1의 길이를 갖는 리스트 생성 소수면 True, 아니라면 False를 갖는 에라토스테네스의 체를 구현

- 그 다음 테스트케이스를 입력받고 각 수를 입력받는다.

- 골든바흐의 추측에 따르면 2보다 큰 짝수 n은 a + b의 형태로 이루어져 있기 때문에 입력받은 수 n에 대하여 2부터 n/2까지 반복문을 돌리고, a, b(=n-a)가 모두 소수(prime[a] == True ad prime[b] == True)일 때 카운트를 틀려나간다.

 

 

알게된 점

- 시간복잡도에서 계속 걸렸다.

- 에라토스테네스의 체를 구현하면서 소수들을 전부 빼낸 후 입력받은 수 n에 대하여 이중 for문으로 풀이하려고 했다.

- 생각해보니 굳이 문제를 보니까 n = i + (n-i)와 동일하다는 것을 알게 되었고, 해시를 사용할 필요도 없이 그냥 prime 리스트의 True/False값만으로 풀 수 있었다.

- 센스... 센스가 부족하다!

 

 

참고 사이트

-