문제이해
처음에 생각했던건
- 들어온 n값에 대해 소수를 구한다.
- 가장 작은 소수를 뺀다.
- 그 뺀값이 구한 소수들로 합쳐진 값이 나온다면 그것이 골드바흐 파티션이다.
- 나오지 않는다면 다음 소수 리스트로 넘어간다.
이렇게 했더니 시간초과가 나옵니다.
다른방법을 써야할 거 같습니다.
코드
#소수를 구하는 함수
def prime_num(n):
a = [False, False] + [True] * (n-1)
b = []
#에라토스테네스의 체로 리스트a를 조정한다.
for i in range(2, n+1):
if(a[i]):
for j in range(i*2, n +1, i):
a[j] = False
#리스트a가 True일 때 인덱스를 출력
for i in range(n+1):
#소수이면
if(a[i]):
b.append(i)
#소수 판별
for j in b[::-1]:
num = n - j #첫 번째 소수를 뺀다.
if(num>1 and a[num]): #1이상 소수들만
for k in b:
if((j + k) == n): #같은 값 중에서
if(j <= k): #두 소수의 차이가 가장 적은 것
print(j, k)
return
#나머지를 소수 리스트로 돌려서 합친 값이 나오면 그것이 골드바흐 파티션
#나오지 않는다면 다음 소수 리스트로 넘어간다.
case = int(input())
while(case > 0):
test_case = int(input())
prime_num(test_case)
case -= 1
다른 방식을 생각 해보니
입력받은 값을 2로 나누고
몫부터 소수를 구하면 되지 않을까? 생각했습니다.
for i in range(n//2,n+1):
#소수라면
if(a[i]):
if(a[n - i]):
print(n-i, i)
return
원래 소수를 구하고 리스트로 만들었던 로직이였습니다.
여기서 주어진값(n)을 2로 나눈 몫(n//2)부터 주어진 값(n)까지 실행하면
중간에서 가장 가까운 값이 "두 소수의 차이가 가장 작은 것" 이 되니
주어진 값(n) 에서 소수를 뺀 값이 주어진 값(n)이라 생각하지말고 그냥 소수라면? 이라는 생각이 더 문제에 맞다고 생각했습니다.
그래서 n-소수, 소수 를 출력하고 가장 가까운 값이 출력이 되었으니 함수는 종료되야 합니다.
다시 생각한 코드
#소수를 구하는 함수
def prime_num(n):
a = [False, False] + [True] * (n-1)
b = []
#에라토스테네스의 체로 리스트a를 조정한다.
for i in range(2, n+1):
if(a[i]):
for j in range(i*2, n +1, i):
a[j] = False
for i in range(n//2,n+1):
#소수라면
if(a[i]):
if(a[n - i]):
print(n-i, i)
return
#입력받은 만큼만 while문 돈다.
case = int(input())
while(case > 0):
test_case = int(input())
prime_num(test_case)
case -= 1
728x90
'알고리즘 > 백준알고리즘' 카테고리의 다른 글
[백준 알고리즘/Python3] 1085 직사각형에서 탈출 (0) | 2021.12.06 |
---|---|
[백준 알고리즘/Python3] 1085 직사각형에서 탈출 (0) | 2021.12.05 |
[백준 알고리즘/Python3] 4948 베르트랑 공준 (0) | 2021.12.02 |
[백준 알고리즘/Python3] 1929 에라토스테네스의 체 (0) | 2021.10.31 |
[백준 알고리즘/Python3] 11653 소인수분해 (0) | 2021.10.28 |