골드바흐의 추측
문제
1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다.
골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다.
2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고 짝수 n이 주어진다.
출력
각 테스트 케이스에 대해서 주어진 n의 골드바흐 파티션을 출력한다. 출력하는 소수는 작은 것부터 먼저 출력하며, 공백으로 구분한다.
내 풀이
import sys, math
# 예제 입력
# 3
# 8
# 10
# 16
sys.stdin = open('example.txt', 'r')
input = sys.stdin.readline().strip()
testCases = int(input)
# print(input)
def isPrimeNumber(num):
for i in range(2, int(math.sqrt(num))+1):
if num % i ==0:
return False
return True
for _ in range(testCases): # testCase만큼 순회만 함
case = int(sys.stdin.readline().strip())
# print(case)
caseArr = []
for i in range(int(case/2)):
# print(case/2 -i, case/2 +i)
if isPrimeNumber(case/2):
caseArr.append(int(case/2))
caseArr.append(int(case/2))
elif isPrimeNumber(case/2 -i) and isPrimeNumber(case/2 +i):
caseArr.append(int(case/2 -i))
caseArr.append(int(case/2 +i))
print(*caseArr[0:2])풀이는 정답인것 같았지만 시간 초과로 나온다...
다른 사람 풀이
import sys, math
# 예제 입력
# 3
# 8
# 10
# 16
sys.stdin = open('example.txt', 'r')
input = sys.stdin.readline().strip()
testCases = int(input)
def isPrimeNumber(num):
if num == 1:
return False
for i in range(2, int(math.sqrt(num))+1):
if num % i ==0:
return False
return True
for _ in range(testCases): # testCase만큼 순회만 함
case = int(sys.stdin.readline().strip())
a, b = case//2, case//2
while a > 0:
if isPrimeNumber(a) and isPrimeNumber(b):
print(a, b)
break
else:
a -= 1
b += 1[백준] 9020 골드바흐의 추측(실버1) - Python의 풀이를 참조하였다.
이 문제는 제곱근 범위 나누기법이라는 개념을 알고있으면 좋다.
제곱근 범위 나누기법이란 어떤 수의 제곱근을 기준으로 그 곱은 대칭적으로 곱이 일어나므로 제곱근 이하의 작은 수까지만 검사하면 나머지는 검사할 필요가 없다는 방법이다.
제곱근 범위 나누기법을 활용해서 어떤 수가 소수인지 아닌지를 판별하는 isPrimeNumber 라는 함수를 만들었다.
그리고 이 문제에서는 주어진 수를 반으로 나누어서 하나는 오른쪽 하나는 왼쪽으로 이동하면서 두 수의 합이 같게 한는 접근을 하는것이 중요하다.
예를 들어 16이라는 수가 주어진다면 반으로 나누어 8이라는 수를 만들고 하나는 오른쪽으로 한칸(1을 더함) 이동하여 9, 또다른 왼쪽으로 한칸(1을 뺌) 이동하여 두 수의 합이 같으면서 각각의 수가 소수인지 아닌지 확인하는 것이다.
이를 반복하여 소수인 수 두개를 더해서 입력한 값이 나오도록 할 수 있다.
이 문제를 풀면서 공부한 내용
python에서 제곱근 구하는법
1. math 모듈 사용
import math
print("2의 루트 : ", math.sqrt(2)) # 2의 루트 : 1.414~~ math 모듈을 import하여 sqrt 메서드를 사용한다.
2. 제곱을 표현하는 연산자 **를 활용한 방법
파이썬에서 m의 n제곱은 **로 표현한다.
4 ** 2 # 16
3 ** 5 # 243
1.5 ** 3 # 3.375
0.1 ** 4 # 0.00010000000000000002(부동 소수점 오차)n 자리에 0.5 또는 1/2을 넣으면 제곱근을 나타낼 수 있다.(1/3, 1/4 등으로 세제곱근, 네제곱근도 가능하다.)
9 ** 0.5 # 3.0
8 ** (1/3) # 2.0
4 ** 1.5 # 8.0
1.5 ** 2.3 # 2.5410306047779248소수 여부를 판단하는 알고리즘
제곱근 범위 나누기법
어떤 수의 약수는 가운데 약수를 기준으로 곱셈 연산에 대해 대칭을 이룬다.
그 이유는 간단하다.
어떤 수의 약수는 양쪽 끝을 곱하면 자기 자신이 되는데
그 수의 제곱근 곱하기 그 수의 제곱근은 자기 자신이 되고 즉 중간에 위치하게된다.
제곱근 범위 나누기법이란 어떤 수의 제곱근을 기준으로 그 곱은 대칭적으로 곱이 일어나므로 제곱근 이하의 작은 수까지만 검사하면 나머지는 검사할 필요가 없다는 방법이다.
제곱근 범위 나누기법을 이용하여 소수인지 아닌지를 확인하는 파이썬 알고리즘은 다음과 같다.
def isPrimeNumber(num):
if num == 1:
return False
for i in range(2, int(math.sqrt(num))+1):
if num % i ==0:
return False
return True파이썬의 Spread Operator(펼침 연산자)
파이썬에서는 *를 통해 컨테이너 타입의 데이터를 unpacking 할 수 있다.
자바스크립트의 ...과 같은 역할을 하는 연산자다.
a = [1 ,3]
print(*a) # 1 3