[17103] 골드바흐 파티션 in python

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

17103번: 골드바흐 파티션

---

처음에 소수 구할때

에라토스테네체 방식을 떠올리지 못했다 ㅎㅎ...

왜 항상 떠올리지 못하는 걸까.. 이런 바부..

 

심지어 이렇게 정리까지 해놓고..

https://eboong.tistory.com/398

[n15965] k번째 소수 in python

 

바보였던 나는 그렇게

 해당하는 모든 수의 소수를 판별하였고..

시간 초과라는 결과를 맞이하였따!

예!

 

그래서 시간초과를 해결하기 위해

서칭을 해 본 결과

에라토스테네체의 존재를 떠올리게 되었고...

 

그 방식을 이용해서 답을 구해냈으나!

또 시간 초과!

 

t = int(input())
MAX=1000000
array = [1 for _ in range(MAX + 1)]
prime = []

# 소수 집합 구하기
for i in range(2, MAX + 1):
    # 에라토스테네체 = 소수!!!
    if array[i]:
        prime.append(i)
        for j in range(i * 2, MAX + 1, i):
            # 배수 지우는 작업
            if j > MAX:
                break
            array[j] = 0

for _ in range(t):
    n=int(input())
    answer = 0
    # 파티션 개수
    for i in range(2, n // 2 + 1):
        if i in prime and n - i in prime:
            answer += 1
    print(answer)

 

if i in prime and n-i in prime 때문에

시간초과가 걸렸다는 걸 

여러번 시도 끝에 알아낸 나자신...

 

prime 리스트의 존재가 필요없어졌으니

바로 삭제하였다!

 

그리고 array에서 인덱스를 통해

값을 바로 찾아가게끔 

코드를 다시 작성하였더니!

 

시간 3356ms

일단 성공은 했지만

탐색 시간이 꽤 오래 나왔다 

 

그래서 고수님들의 코드를 슥슥 살펴보기로 결심했다.

 

t = int(input())
MAX=1000000
array = [1 for _ in range(MAX + 1)]

# 소수 집합 구하기
for i in range(2, MAX + 1):
    # 에라토스테네체 = 소수!!!
    if array[i]:
        for j in range(i * 2, MAX + 1, i):
            # 배수 지우는 작업
            if j > MAX:
                break
            array[j] = 0

for _ in range(t):
    n=int(input())
    answer = 0
    # 파티션 개수
    for i in range(2, n // 2 + 1):
        if array[i] and array[n-i]:
            answer += 1
    print(answer)

---

for문 부분을 바꿔줬더니

탐색시간이 줄었다! 약 1200ms

 

n-i 의 값이 i 값보다 작을 경우

for문을 중단시키는 과정은 

범위 에러 발생 방지하는 부분

 

prime 리스트가 오히려 시간만 더 걸리게 하는 줄 알았는데

사용하는 방식이 잘못 되어서 그런것이었다...ㅎ

 

t = int(input())
MAX = 1000000
array = [1 for _ in range(MAX + 1)]
prime = []

# 소수 집합 구하기
for i in range(2, MAX + 1):
    # 에라토스테네체 = 소수!!!
    if array[i]:
        prime.append(i)
        for j in range(i * 2, MAX + 1, i):
            # 배수 지우는 작업
            if j > MAX:
                break
            array[j] = 0

for _ in range(t):
    n = int(input())
    answer = 0
    for i in prime:
        if n - i < i:
            break
        if array[n - i]:
            answer += 1
    print(answer)