알고리즘, 코딩테스트/BOJ 문제풀이
[python] BOJ 백준 소수 관련 문제 - 1929, 6588 :: 소수구하기, 골드바흐의 추출
우징어🦑
2021. 2. 8. 14:33
1929번: 소수 구하기
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
www.acmicpc.net
n,m = map(int, input().split())
check = [False]*(m+1)
for i in range(2, m+1):
if check[i] == False:
for j in range(i*2, len(check), i):
check[j] = True # True: 소수가 아닌 수
if n==1:
for i in range(2,m+1):
if check[i] == False:
print(i)
else:
for i in range(n,m+1):
if check[i] == False:
print(i)
6588번: 골드바흐의 추측
각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰
www.acmicpc.net
import sys
# 6<= 입력수<=1000000
n = 1000000
check = [False] * (n+1)
prime = []
for i in range(2, n+1):
if check[i] == False:
for j in range(i*2, n+1, i):
check[j] = True # 소수가 아닌 수
for x in range(2, n+1):
if check[x] == False: # 소수이면
prime.append(x)
while True:
num = int(input())
if num == 0:
sys.exit()
for p in prime:
if check[num-p] == False:
print('{0} = {1} + {2}'.format(num, p, num-p))
break