[python] BOJ 백준 소수 관련 문제 - 1929, 6588 :: 소수구하기, 골드바흐의 추출

www.acmicpc.net/problem/1929

1929번: 소수 구하기

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)

 

 

www.acmicpc.net/problem/6588

6588번: 골드바흐의 추측

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