골드바흐의 추측 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
| 0.5 초 | 256 MB | 70579 | 13002 | 8846 | 23.142% |
문제
1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.
4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.
예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다.
이 추측은 아직도 해결되지 않은 문제이다.
백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.
입력
입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다.
각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ≤ 1000000)
입력의 마지막 줄에는 0이 하나 주어진다.
출력
각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력한다. 또, 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력한다.
예제 입력 1
8
20
42
0
예제 출력 1
8 = 3 + 5
20 = 3 + 17
42 = 5 + 37
풀이
1) 시간 초과로 오답
def eratosthenes_sieve(n):
is_prime = [True] * (n+1)
is_prime[0], is_prime[1] = False, False
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
for j in range(i*i, n+1, i):
is_prime[j] = False
return is_prime
def goldbach_conjecture(n, primes):
for a in range(3, n // 2 + 1, 2):
if primes[a] and primes[n - a]:
return a, n - a
return None
if __name__ == "__main__":
MAX_N = 1000000
primes = eratosthenes_sieve(MAX_N)
while True:
n = int(input())
if n == 0:
break
a, b = goldbach_conjecture(n, primes)
if a and b:
print(f"{n} = {a} + {b}")
else:
print("Goldbach's conjecture is wrong.")- 풀이과정
def eratosthenes_sieve(n):에라토스테네스의 체 알고리즘을 사용하여 소수를 구하는 함수를 정의합니다.
is_prime = [True] * (n+1)소수 여부를 확인하기 위한 리스트를 생성하고, 모든 인덱스의 값을 True로 초기화합니다. 리스트의 길이는 n+1로 설정하여 인덱스를 직접 수로 사용할 수 있게 합니다.
is_prime[0], is_prime[1] = False, False0과 1은 소수가 아니므로, 해당 인덱스의 값을 False로 변경합니다.
for i in range(2, int(n**0.5) + 1):2부터 n의 제곱근까지의 정수 i에 대해 반복문을 실행합니다.
if is_prime[i]:i가 소수인 경우 (is_prime[i]가 True인 경우), 다음 코드를 실행합니다.
for j in range(i*i, n+1, i):i의 제곱부터 n까지 i씩 증가하는 정수 j에 대해 반복문을 실행합니다.
is_prime[j] = Falsej를 i로 나눌 수 있으므로, j는 소수가 아닙니다. 따라서 is_prime[j]를 False로 변경합니다.
return is_prime모든 소수의 여부를 확인한 리스트를 반환합니다.
def goldbach_conjecture(n, primes):골드바흐 추측을 검증하는 함수를 정의합니다. 입력값으로 짝수 정수 n과 소수 여부 리스트를 받습니다.
for a in range(3, n // 2 + 1, 2):3부터 n의 절반까지 2씩 증가하는 홀수 정수 a에 대해 반복문을 실행합니다.
if primes[a] and primes[n - a]:a와 (n-a)가 모두 소수인 경우, 다음 코드를 실행합니다.
return a, n - aa와 (n-a)를 반환합니다.
return None두 홀수 소수의 합으로 n을 나타낼 수 없는 경우, None을 반환합니다.
if __name__ == "__main__":파이썬 스크립트가 직접 실행되는 경우에만 다음 코드를 실행합니다.
MAX_N = 1000000최대 입력값을 상수로 지정합니다.
primes = eratosthenes_sieve(MAX_N)최대 입력값까지의 소수 여부를 확인하는 리스트를 생성합니다.
while True:계속해서 입력을 받기 위한 무한 루프를 시작합니다.
n = int(input())짝수 정수 n을 입력받습니다.
if n == 0:만약 입력받은 값이 0이라면,
break무한 루프를 종료합니다.
a, b = goldbach_conjecture(n, primes)입력받은 짝수 정수 n에 대해 골드바흐 추측을 검증하고, 두 홀수 소수 a와 b를 반환받습니다.
if a and b:a와 b가 모두 존재하는 경우 (두 홀수 소수의 합으로 n을 나타낼 수 있는 경우),
print(f"{n} = {a} + {b}")n, a, b를 출력합니다.
else:a와 b가 모두 존재하지 않는 경우 (두 홀수 소수의 합으로 n을 나타낼 수 없는 경우),
print("Goldbach's conjecture is wrong.")골드바흐 추측이 잘못되었다는 문구를 출력합니다.
2) 수정한 코드
import sys
def eratosthenes_sieve(n):
is_prime = [True] * (n+1)
is_prime[0], is_prime[1] = False, False
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
for j in range(i*i, n+1, i):
is_prime[j] = False
return is_prime
def goldbach_conjecture(n, primes, prime_list):
for a in prime_list:
if a > n // 2:
break
if primes[n - a]:
return a, n - a
return None
if __name__ == "__main__":
MAX_N = 1000000
primes = eratosthenes_sieve(MAX_N)
prime_list = [i for i in range(3, MAX_N, 2) if primes[i]]
while True:
n = int(sys.stdin.readline())
if n == 0:
break
a, b = goldbach_conjecture(n, primes, prime_list)
if a and b:
print(f"{n} = {a} + {b}")
else:
print("Goldbach's conjecture is wrong.")- 풀이과정
먼저
import sys를 사용하여sys.stdin.readline을 사용할 수 있도록 합니다.import syseratosthenes_sieve함수는 에라토스테네스의 체 알고리즘을 사용하여 주어진 범위 내의 소수 여부를 판별하는 리스트를 생성해 반환합니다.def eratosthenes_sieve(n): is_prime = [True] * (n+1) is_prime[0], is_prime[1] = False, False for i in range(2, int(n**0.5) + 1): if is_prime[i]: for j in range(i*i, n+1, i): is_prime[j] = False return is_prime→
for j in range(i*i, n+1, i)구문 해석i*i부터 시작하고i씩 증가시키는 이유는 에라토스테네스의 체 알고리즘에서 중복 처리를 최소화하고 효율적으로 합성수를 제거하기 위함입니다.i*i부터 시작하는 이유: 현재 숫자i보다 작은 수들에 대해서는 이미 이전 단계에서 그 배수들을 제거한 상태입니다. 예를 들어,i=3일 때, 2의 배수들은 이미 처리되었습니다. 따라서i가 3일 때, 2와 3의 곱인 6을 처리할 필요가 없습니다. 이와 같은 원리로,i의 배수 중에서i이전의 소수들과의 곱은 이미 처리되었으므로,i*i부터 시작하는 것이 효율적입니다.
i씩 증가시키는 이유:i의 배수를 제거하기 위해i씩 증가시킵니다. 이 과정에서i의 배수들은 소수가 아닌 합성수로 처리됩니다. 이렇게i씩 증가시키면서 진행하면, 해당 소수의 모든 배수들을 효율적으로 제거할 수 있습니다.
요약하면,
i*i부터 시작하고i씩 증가시키는 것은 에라토스테네스의 체 알고리즘을 효율적으로 구현하기 위한 것입니다. 이렇게 하면 중복 처리를 최소화하고 소수 여부를 빠르게 판별할 수 있습니다.goldbach_conjecture함수는 주어진 짝수 정수 n에 대해 골드바흐 추측을 검증하고, 만족하는 두 홀수 소수 a와 b를 반환합니다. 이때, 함수 내부의 반복문은 미리 구해 둔 홀수 소수 리스트인prime_list를 사용합니다.def goldbach_conjecture(n, primes, prime_list): for a in prime_list: if a > n // 2: break if primes[n - a]: return a, n - a return None→
if a > n // 2구문 해석골드바흐 추측은 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다고 말합니다. 여기서 주어진 짝수는
n입니다. 이를 두 홀수 소수의 합으로 나타내려면, 두 소수 중 하나는n // 2보다 작거나 같아야 합니다. 이유는 두 홀수 소수 모두n // 2보다 크다면, 그 합은n보다 커지게 되기 때문입니다.예를 들어,
n = 20이라고 가정해봅시다. 20은 두 홀수 소수의 합으로 나타낼 수 있습니다. 두 홀수 소수 중 하나가 20 // 2 = 10보다 작거나 같아야 합니다. 예를 들어, 3과 17의 경우 3 + 17 = 20이며, 이때 3은 10보다 작습니다. 만약 두 홀수 소수 모두 10보다 크다면, 예를 들어 11과 13의 경우, 합은 24로n보다 커집니다.따라서 이 반복문에서는 소수 목록
prime_list의 원소a를 순회하면서 골드바흐 추측을 만족하는 두 홀수 소수를 찾습니다.a가n // 2보다 크게 되면, 그 이후의 소수들을 확인할 필요가 없기 때문에 반복문을 종료합니다.메인 코드에서는 먼저 에라토스테네스의 체를 사용하여 MAX_N 범위 내의 소수 여부를 판별하는 리스트를 생성하고, 홀수 소수만 따로
prime_list에 저장합니다.if __name__ == "__main__": MAX_N = 1000000 primes = eratosthenes_sieve(MAX_N) prime_list = [i for i in range(3, MAX_N, 2) if primes[i]]그 다음,
sys.stdin.readline을 사용하여 빠르게 입력을 받고, 각각의 짝수 정수에 대해 골드바흐 추측을 검증합니다. 검증 결과를 출력하고, 입력 값이 0일 때까지 이 과정을 반복합니다.while True: n = int(sys.stdin.readline()) if n == 0: break a, b = goldbach_conjecture(n, primes, prime_list) if a and b: print(f"{n} = {a} + {b}") else: print("Goldbach's conjecture is wrong.")미리 소수를 구해두고 홀수 소수 리스트를 사용함으로써, 시간 초과 문제를 해결할 수 있습니다.
3) 다른 코드
MAX = 1000000
check = [0]*(MAX+1)
check[0] = check[1] = True
prime = []
for i in range(2, MAX+1):
if not check[i]:
prime.append(i)
j = i+i
while j <= MAX:
check[j] = True
j += i
prime = prime[1:]
while True:
n = int(input())
if n == 0:
break
for p in prime:
if check[n-p] == False:
print("{0} = {1} + {2}".format(n, p, n-p))
break- 풀이과정
먼저,
MAX변수를 사용하여 범위를 지정하고, 소수 여부를 확인할 수 있는check리스트를 생성합니다.check리스트의 인덱스가 소수일 경우False, 소수가 아닐 경우True로 설정됩니다.MAX = 1000000 check = [0]*(MAX+1) check[0] = check[1] = Trueprime리스트는 소수를 저장할 리스트입니다. 에라토스테네스의 체를 사용하여 소수를 판별하고, 소수인 경우prime리스트에 추가합니다.prime = [] for i in range(2, MAX+1): if not check[i]: prime.append(i) j = i+i while j <= MAX: check[j] = True j += i그 다음, 2를 제외한 홀수 소수만 남기기 위해
prime리스트에서 첫 번째 원소를 제거합니다.prime = prime[1:]이제 입력을 받아서 골드바흐 추측을 검증합니다. 입력 값이 0일 때까지 반복합니다.
while True: n = int(input()) if n == 0: break각 테스트 케이스에 대해, 홀수 소수 리스트인
prime을 사용하여 두 홀수 소수의 합으로 n을 만들 수 있는지 확인합니다. 가능한 경우 출력하고, 반복문을 종료합니다.for p in prime: if check[n-p] == False: print("{0} = {1} + {2}".format(n, p, n-p)) break이 코드도 골드바흐 추측을 검증하는 알고리즘을 효율적으로 구현하였습니다. 에라토스테네스의 체를 사용하여 미리 소수를 구하고, 이를 활용하여 각 테스트 케이스에 대해 빠르게 검증할 수 있습니다.
Uploaded by N2T
'Algorithm' 카테고리의 다른 글
| [백준 17087 파이썬/python] 숨박꼭질 6 (0) | 2023.04.10 |
|---|---|
| [백준 9613 파이썬/python] GCD 합 (0) | 2023.04.10 |
| [백준 1929 파이썬/python] 소수 구하기 (0) | 2023.04.09 |
| [백준 2609 파이썬/python] 최대공약수와 최소공배수 (0) | 2023.04.09 |
| [백준 1934 파이썬/python] 최소공배수 (0) | 2023.04.09 |
