job다한 공부

백준 6588번: 골드바흐의 추측-파이썬(python) 본문

백준/알고리즘 1

백준 6588번: 골드바흐의 추측-파이썬(python)

시현한 하루 2022. 10. 5. 16:21
728x90

https://www.acmicpc.net/problem/6588

 

6588번: 골드바흐의 추측

각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#골드바흐의 추측
import sys
lst=[1 for i in range(1000000)]
lst[1]=0
for i in range(2,int((1000000)**0.5)+1):  #홀수 소수의 합이어야함
    if lst[i]!=0:
        for j in range(2*i,1000000,i):
            lst[j]=0
 
 
while(True):
    n=int(sys.stdin.readline().rstrip())
    if n==0:
        break
    for j in range(3,n): 
        if lst[j]==True and lst[n-j]==True:
            print(n,'=',j,'+',n-j)
            break
    if j==n-1:
        print("Goldbach's conjecture is wrong.")
 
    
 
 cs

-이전 문제와는 다르게 홀수로만 이루어진 합을 찾아야했다.

728x90

'백준 > 알고리즘 1' 카테고리의 다른 글

백준 11047번: 동전 0-파이썬(python)  (0) 2022.10.06
백준 1676번: 팩토리얼 0의 개수-파이썬(python)  (2) 2022.10.05
백준 10824번: 네 수-파이썬(python)  (0) 2022.10.03
백준 2609번: 최대공약수와 최소공배수-파이썬(python)  (0) 2022.10.02
백준 1158번: 요세푸스 문제-파이썬(python)  (0) 2022.10.01
'백준/알고리즘 1' Related Articles more