[백준] 15단계: 약수, 배수와 소수 2

1. [1934] 최소공배수 

두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다. 두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.

T = int(input())
for _ in range(T):
    A, B = map(int, input().split())
    AA, BB = A, B
    while BB != 0: # 최대공약수 구하기
        AA = AA % BB
        AA, BB = BB, AA
    print(A*B//AA) # 각 수 곱하여 최대공약수로 나눠주기

2. [13241] 최소공배수

정수 B에 0보다 큰 정수인 N을 곱해 정수 A를 만들 수 있다면, A는 B의 배수이다.

예:

• 10은 5의 배수이다 (5*2 = 10)
• 10은 10의 배수이다(10*1 = 10)
• 6은 1의 배수이다(1*6 = 6)
• 20은 1, 2, 4,5,10,20의 배수이다.

다른 예:

• 2와 5의 최소공배수는 10이고, 그 이유는 2와 5보다 작은 공배수가 없기 때문이다.
• 10과 20의 최소공배수는 20이다.
• 5와 3의 최소공배수는 15이다.

당신은 두 수에 대하여 최소공배수를 구하는 프로그램을 작성 하는 것이 목표이다.

A, B = map(int, input().split())
for i in range(1, A+1):
    if (A % i == 0) & (B % i == 0):
        gcd = i
if gcd == 1:
    print(A*B)
else:
    print(A*B//gcd)

3. [1735] 분수합

분수 A/B는 분자가 A, 분모가 B인 분수를 의미한다. A와 B는 모두 자연수라고 하자. 두 분수의 합 또한 분수로 표현할 수 있다. 두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구하는 프로그램을 작성하시오. 기약분수란 더 이상 약분되지 않는 분수를 의미한다.

def gcd(x, y):
    mod = x % y
    while mod != 0:
        x = y
        y = mod
        mod = x % y
    return y

A, B = map(int, input().split())
C, D = map(int, input().split())
numerator = A*D+C*B
denominator = B*D
num = gcd(numerator, denominator)
print(int(numerator//num), int(denominator/num))

4. [2485] 가로수

직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. KOI 시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있다. KOI 시에서는 예산문제로 가능한 한 가장 적은 수의 나무를 심고 싶다. 편의상 가로수의 위치는 기준점으로 부터 떨어져 있는 거리로 표현되며, 가로수의 위치는 모두 양의 정수이다. 예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 심으면 모든 가로수들의 간격이 같게 된다. 또한, 가로수가 (2, 6, 12, 18)에 있다면 (4, 8, 10, 14, 16)에 가로수를 더 심어야 한다. 심어져 있는 가로수의 위치가 주어질 때, 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 구하는 프로그램을 작성하라. 단, 추가되는 나무는 기존의 나무들 사이에만 심을 수 있다.

def gcd_func(x, y):
    while y != 0:
        x, y = y, x % y
    return x

N = int(input())

n_list = [int(input()) for _ in range(N)]

n_difference = []
for i in range(1, N):
    n_difference.append(n_list[i] - n_list[i - 1])

diff_set = list(set(n_difference))

gcd = diff_set[0]
for i in range(1, len(diff_set)):
    gcd = gcd_func(gcd, diff_set[i])

cnt = 0
for duff in n_difference:
    cnt += duff // gcd - 1
print(cnt)

5. [4134] 다음 소수

정수 n(0 ≤ n ≤ 4*10^9)가 주어졌을 때, n보다 크거나 같은 소수 중 가장 작은 소수 찾는 프로그램을 작성하시오.

import math
def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(math.sqrt(num)+1)):
        if num % i == 0:
            return False
    return True

n = int(input())
for _ in range(n):
    num = int(input())
    while True:
        if is_prime(num):
            print(num)
            break
        else:
            num += 1

※ 6~7번은 이전에 풀었던 문제라 생략합니다.

 

8. [17103] 골드바흐 파티션

• 골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.

짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.

## 에라토스테네스의 체
prime_list = [False, False] + [True]*999999
for i in range(2, 1000001):
    if prime_list[i]:
        for j in range(i*2, 1000001, i):
            prime_list[j] = False

import sys
input = sys.stdin.readline
T = int(input())

# 골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.
for _ in range(T):
    N = int(input())
    result = 0
    for j in range(2, N // 2 + 1):
        if prime_list[j] and prime_list[N-j]:
            result += 1
    print(result)

9. [13909] 창문 닫기

서강대학교 컴퓨터공학과 실습실 R912호에는 현재 N개의 창문이 있고 또 N명의 사람이 있다. 1번째 사람은 1의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다.  2번째 사람은 2의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 이러한 행동을 N번째 사람까지 진행한 후 열려 있는 창문의 개수를 구하라. 단, 처음에 모든 창문은 닫혀 있다.

예를 들어 현재 3개의 창문이 있고 3명의 사람이 있을 때,

1. 1번째 사람은 1의 배수인 1,2,3번 창문을 연다. (1, 1, 1)
2. 2번째 사람은 2의 배수인 2번 창문을 닫는다. (1, 0, 1)
3. 3번째 사람은 3의 배수인 3번 창문을 닫는다. (1, 0, 0)

결과적으로 마지막에 열려 있는 창문의 개수는 1개 이다.

N = int(input())
x = 1
result = 0
while x*x <= N:
    x += 1
    result += 1
print(result)