[Baekjoon] 1978번 : 소수찾기 / 1929번 : 소수 구하기 / 4948번 : 베르트랑 공준 / 9020번 : 골드바흐의 추측

소수 관련 문제들

첫 번째 소수찾기 문제는 반복문으로 1씩 증가시키면서 나눠 떨어지면 소수가 아닌 것으로 판단하는 방식을 사용했다.

하지만 범위가 큰 문제들의 경우 동일한 방식을 사용하면 시간 초과가 발생한다.

 

에르토스테네스의 체를 기억해두자!

 

# 소수 찾기

1978번: 소수 찾기

n = int(input())
nums = list(map(int, input().split()))

def check_num(num):
    for i in range(2, num):
        if num % i == 0:
            return 0
    return 1

count = 0
for num in nums:
    if num != 1:
        count += check_num(num)

print(count)

 

# 소수 구하기 

1929번: 소수 구하기

에라토스테네스의 체를 사용해야 시간초과 없이 해결할 수 있다.

에라토스테네스의 체란 일정 범위 내 수열에서 배수인 것들을 제거하여 소수만 남기는 방식을 말한다.중복되는 값들이 있어 끝 값의 제곱근까지만 검사하면 된다.

 

start, end = map(int, input().split())
# 끝 숫자를 포함하기 위해 1을 더함
end = end+1
# 소수인지 여부를 저장할 리스트
check_num = [True] * end

for i in range(2, int(end**0.5)+1):
    if check_num[i]:
        for j in range(2*i, end, i):
            check_num[j] = False
            
for i in range(start, end):
    # 1보다 크고 소수이면 출력
    if i > 1 and check_num[i] == True:
        print(i)

 

# 베르트랑 공준

4948번: 베르트랑 공준

n이 입력될 때 n보다 크고 2n보다 작거나 같은 숫자들 중 소수가 몇 개인지 구하는 문제

마찬가지로 에라토스테네스의 체를 사용하면 시간 초과 없이 해결가능

 

while True:
    num = int(input())

    start, end = num, num*2+1
    count = 0
    check_num = [True] * end
    if num == 0:
        break

    for i in range(2, int(end**0.5)+1):
        # 배수인 경우 소수가 아님
        if check_num[i]:
            for j in range(2*i, end, i):
                check_num[j] = False

    for i in range(start, end):
        if i>start and check_num[i] == True:
            count += 1

    print(count)

 

# 골드바흐의 추측

9020번: 골드바흐의 추측

골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 

 

2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램 작성하기(가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력)

 

t = int(input())

limit = 10001
check_num = [True] * limit

for i in range(2, int(limit ** 0.5) + 1):
    if check_num:
        for j in range(2 * i, limit, i):
            check_num[j] = False

for _ in range(t):
    num = int(input())
    min_value = 10001
    answer_a, answer_b = 0, 0

    end = int(num / 2) + 1 # 절반까지만 체크
    for first in range(end):
        if first>1 and check_num[first] == True:
            second = num - first  # 주어진 짝수 - 소수1

            if check_num[second] == True:
                diff = second - first
                if min_value > diff:
                    min_value = diff
                    answer_a, answer_b = first, second

    print(answer_a, answer_b)

중복되는 반복문을 최대한 줄일 수 있도록 정리해야 시간초과를 피할 수 있다.