문제
4 이상의 짝수에 대해 골드바흐 추측을 만족하면서 두 소수간 차이가 가장 작은 수를 출력하시오.
Reference
https://deokkk9.tistory.com/20
https://github.com/tsamoglou/Goldbach-s-Weak-Conjecture/blob/master/PrimeNumbers.py (이쪽은 응용편 참고문헌)
풀이
일단 골드바흐의 추측은 두 개가 있는데, 하나는 강한 추측이고 다른 하나는 약한 추측이다.
2보다 큰 모든 짝수는 소수 두 개의 합으로 정의할 수 있다.
골드바흐
이게 강한 추측(문제에 나오는 것)
5보다 큰 모든 홀수는 소수 세 개의 합으로 정의할 수 있다.
골드바흐
이게 약한 추측이다.
그래서 이게 무슨 소리냐고? 12=5+7일 때 5와 7은 소수다. 14=7+7일 때 7은 소수다. 7=2+2+3일 때 2와 3은 소수다. …뭐 그런 얘기다. 여기서 문제는 골드바흐의 강한 추측을 만족하는 순서쌍(중 두 소수간 차가 가장 작은 것)을 출력하는 것.
4 = 2+2
6 = 3+3
8 = 3+5
10 = 3+7 = 5+5
12 = 5+7
14 = 3+11 = 7+7
16 = 3+13 = 5+11
18 = 5+13 = 7+11
20 = 3+17 = 7+13
22 = 3+19 = 5+17 = 11+11
24 = 5+19 = 7+17 = 11+13
26 = 3+23 = 7+19 = 13+13
28 = 5+23 = 11+17
30 = 7+23 = 11+19 = 13+17
32 = 3+29 = 13+19
34 = 3+31 = 5+29 = 11+23 = 17+17
36 = 5+31 = 7+29 = 13+23 = 17+19
38 = 7+31 = 19+19
40 = 3+37 = 11+29 = 17+23
42 = 5+37 = 11+31 = 13+29 = 19+23
44 = 3+41 = 7+37 = 13+31
46 = 3+43 = 5+41 = 17+29 = 23+23
48 = 5+43 = 7+41 = 11+37 = 17+31 = 19+29
50 = 3+47 = 7+43 = 13+37 = 19+314부터 50까지 골드바흐 추측을 만족하는 순서쌍이 이렇게 있는데, 잘 보면 쌍이 하나인 것도 있고 여러개인 것도 있다. 저 여러개인 것들 중, 소수간 차이가 제일 적은 것… 그러니까 맨 뒤에 있는 걸 출력하면 된다.
본편 풀이
import sys
T = int(sys.stdin.readline())
def isprime(a):
sqrt = int(a ** 0.5)
if a == 1:
return False
for i in range(2,sqrt+1):
if a % i == 0:
return False
else:
return True
prime = []
for i in range(4,10001):
if isprime(i):
prime.append(i)이것도 범위가 있는게… 쌩으로 돌리면 응애 나 애기시간초과! 가 반길 것 같으니 리스트부터 만들어보자…
for i in range(T):
N = int(sys.stdin.readline())
for j in prime:
if j < N:
print(j)그리고 이렇게 하면 일단 N보다 작은 소수가 다 나오긴 한다. 근데 우리가 출력하는 형식이 n m이잖아요?
for i in range(T):
N = int(sys.stdin.readline())
for j in prime:
if j < N and N - j in prime:
print(j,N-j)근데 또 이렇게 하면 모든 순서쌍…이 중복으로 나온다. 8을 입력하면 3 5와 5 3이 나오는데 우리는 앞에 있는 수가 더 작은 순서쌍만 볼거임…
for i in range(T):
N = int(sys.stdin.readline())
for j in prime:
if j < N and N - j in prime and j < N - j:
print(j,N-j)아, 저거 저렇게 하면 10이 5 5가 아니라 3 7만 나온다… 그리고 저 중에서 가장 차이가 작은 쌍을 출력하려면 또 뭘 어떻게 해야 하는거냐고…OTL
for i in range(T):
N = int(sys.stdin.readline())
a = N // 2
b = a
while a > 0:
if a in prime and b in prime:
print(a,b)
break
else:
a -= 1
b += 1하던 찰나에 저걸 찾은 것이다.
예를 들어서 8을 입력했다 치면, a와 b는 4가 된다. 그런데 4는 소수가 아니기때문에 목록에 없다. 그러면 a는 1을 빼고, b는 1을 더한 다음 둘 다 소수인지 확인한다. 그리고 둘 다 소수면? Profit!
import sys
T = int(sys.stdin.readline())
def isprime(a):
sqrt = int(a ** 0.5)
if a == 1:
return False
for i in range(2,sqrt+1):
if a % i == 0:
return False
else:
return True
prime = []
for i in range(1,10001):
if isprime(i):
prime.append(i)
for i in range(T):
N = int(sys.stdin.readline())
a = N // 2
b = a
while a > 0:
if a in prime and b in prime:
print(a,b)
break
else:
a -= 1
b += 1그래서 이렇게 내면 맞는다. 시간제한이 촉박하다 싶으면 반복문은 빼거나 최소한의 범위로만 할 수 있게 셋업해주는 게 좋을 듯 하다.
응용편-골드바흐의 약한 추측
역시 미쿡이야… 어지간한건 다 해봤어… 대단함…
import sys
def isprime(a):
sqrt = int(a ** 0.5)
if a == 1:
return False
for i in range(2,sqrt+1):
if a % i == 0:
return False
else:
return True
N = int(sys.stdin.readline())
for i in range(2,N + 1):
if isprime(i):
for j in range(i,N - i):
if isprime(N - i - j) and N - i + j == N:
print(i,j,N - i - j)위에 함수파트는 똑같이 가면 된다. 아래쪽이… i가 소수고 i부터 N-i까지 중에서 N-i-j가 소수이고 N-i+j가 N이랑 같으면… 모르것다… 일단 출력 결과물을 보면서 얘기해보자.
9
2 2 5
3 3 39를 넣었을 때 어떻게 되는가?
- i가 2부터 10까지인데(사실상 9) 2가 isprime을 돌려보니까 소수여
- 아따 그니까 j의 범위가 2에서 6까지(7 미만)인디
- 이 때 N-i-j는 9-2-2인 5다. 그리고 5가 isprime이고 N-i+j는 9-2+2니까 9다.
출(별)력. 이게 1차 루프다.
- i가 3일때 3은 소수니까 isprime을 패스하고
- j의 범위는 3부터 5까지(6 미만)인데
- 9-3-3이 3인디 3이 소수여… 그리고 9-3+3은 9여.
그래서 이렇게 된 거다. 252는 9-2+5가 9가 아니라 뺐나… 혹시 설명을 봐도 이해가 안되면…
https://pythontutor.com/visualize.html#mode=display
여기서 한번 돌려보면 좋음. 참고로 저기는 임포트가 안돼서 sys.stdin.readlinne()을 input()으로 바꿔야 한다. 아 그럼 4는 어디갔냐고? 4는 합성수임다. 5는? 5는 range가 성립이 안된다. (5부터 4 미만이 뭐여)
Reply