[백준] 준비운동 Part1. 튼튼한 기본기2

1. 최대공약수와 최소공배수

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

2609번: 최대공약수와 최소공배수

 

유클리드 호제법 참고(https://myjamong.tistory.com/138)

a, b = map(int, input().split())
lcm = a*b

while True:
    r = a % b #유클리드 호제법
    if r == 0:
        break
    a = b
    b = r

gcd = b
lcm /= b #최소공배수 = a * b / 최대공약수

print(gcd)
print(int(lcm))

 

 

2. N번째 큰 수

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

2693번: N번째 큰 수

t = int(input())

for i in range(t):
    a = list(map(int, input().split()))
    a.sort(reverse=True)
    print(a[2])

 

 

3. 소수 찾기

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

1978번: 소수 찾기

에라토스테네스의 체 활용

import math

n = int(input())
arr = list(map(int, input().split()))
arr.sort()
era = [False, False] + [True]*(arr[-1]-1)

for i in range(2, int(math.sqrt(arr[-1]))+1):
    if era[i]:
        for j in range(2*i, arr[-1]+1, i):
            era[j] = False

answer = 0
for a in arr:
    if era[a]:
        answer += 1

print(answer)

 

 

4. 쉽게 푸는 문제

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

1292번: 쉽게 푸는 문제

st, ed = map(int, input().split())

edsum = 0
stsum = 0
j = 1
cnt = 0
for i in range(1, ed+1):
    edsum += j
    cnt += 1
    if cnt == j:
        j += 1
        cnt = 0
    if i == st-1:
        stsum = edsum

print(edsum - stsum)

https://one-hour.tistory.com/41

x, y = map(int, input().split())
a = []
for i in range(y+1) :
    for j in range(i):
        if len(a) == y :
            break
        a.append(i)
print(sum(a[x-1:y]))

 

 

5. 소수

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

2581번: 소수

다른 사람들은 주로 %연산자를 통해 직접 소수를 체크했던데, 나는 에라토스테네스의 체로 구현했다.

M과 N이 10,000이하의 자연수이기 때문에 최대 10,000개의 소수를 직접 체크해야한다.

이처럼 다수의 소수를 구할때에는 에라토스테네스의 체가 더 적합하다고 생각한다.

직접 소수를 구하는 방법은 구하려는 소수의 개수가 적거나, 체크하려는 수가 매우 커서 배열을 만들 수 없을 때 사용해야 하는 것 같다. (이걸 몰라서 카카오 코테에서 2시간 썼다..)

import math

st = int(input())
ed = int(input())

era = [False, False] + [True]*(ed-1)

primes = []
for i in range(2, int(math.sqrt(ed))+1):
    if era[i]:
        for j in range(i*2, ed+1, i):
            era[j] = False

for i in range(st, ed+1):
    if era[i]:
        primes.append(i)

if len(primes) == 0:
    print(-1)
else:
    print(sum(primes))
    print(primes[0])