글 읽기 - 6588 골드바흐 추측

shh0422 1년 전 0

고수분들 도와주세요 ㅠㅠ

틀렸다구 나오는데 반례를 못찾겠습니다... ㅠ

과정은 다음과 같습니다.

1. 100만까지의 소수 집합을 뽑아내서

2. 안쓸 2를 제거하고

3. 이것을 리스트로 만들어 작은 것부터 정렬한 다음 ( [3, 5, 7, 11, 13, 17, 19, ... ] )

4. 예를 들어 입력으로 100이 들어왔다면 소수 리스트의 원소(prime 이라고 표기하겠습니다)들을 차례로 돌며 100 - prime 이 소수 집합에 있는지 확인했습니다.

5. 있다면 (prime, (100 - prime)) 를 반납하고 없다면 리스트의 다음 원소로 넘어가도록 했습니다.

import math

# N 이하의 소수 집합을 반환하는 함수
def get_primes(N):
    p = {i for i in range(2, N+1)}
    
    for i in range(2, int(math.sqrt(N)) + 1):
        if i not in p:
            continue
        
        cut = i * 2
        while cut <= N:
            p.discard(cut)
            cut += i
            
    return p

# even : 짝수, prime_set : 소수 집합, prime_list : 소수 리스트(정렬된 것이 필요)
def goldbach(even, prime_set, prime_list):
    half = even // 2
    
    for prime in prime_list:
        if prime >= half:
            return None
        
        if even - prime in prime_set:
            return prime, even - prime


N = 10**6
prime_set = get_primes(N)
prime_set.discard(2)
prime_list = sorted(prime_set)

while True:
    even = int(input())
    if even == 0:
        break
    
    result = goldbach(even, prime_set, prime_list)
    if result == None:
        print('Goldbach\'s conjecture is wrong.')
    else:
        print('{0} = {1} + {2}'.format(even, result[0], result[1]))

pill27211 1년 전 0

6 ≤ n

Input)

Output)

Goldbach's conjecture is wrong.

Answer)

6 = 3 + 3

shh0422 1년 전 1

형님 정말 감사합니다!!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

6588 골드바흐 추측

shh0422 1년 전 0

pill27211 1년 전 0

shh0422 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말