[백준] 나머지 연산, 최대공약수, 최소공약수

1. 나머지 연산

정답을 1000,000,007로 나눈 나머지를 출력하자.

구하는 과정에서 나눠서 계산하는 풀이.

1. 덧셈, 곱셈은 매번 나머지 연산을 수행해서 계산해도 된다.

예)

(6+3) % 3 = ((6%3) + (3%3)) % 3

2. 음수일 경우 언어별로 결과가 달라진다.(나는 파이썬이니까 상관 없음)

3. 나눗셈의 경우 잘 안나오니까 일단 패스

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

A,B,C = map(int,input().split())
print(((A + B) % C))
print(((A % C) + (B % C)) % C)
print(((A * B) % C))
print(((A % C) * (B % C)) % C)

2. 최대공약수

중요한 알고리즘

기약분수 형태를 구하기 위해 꼭 있어야 함.

배우기 전에..

약수란? N을 나눌 수 있는 수

예)

24 - 1,2,3,4,6,8,12,24

18 - 1,2,3,6,18

공약수란? 두 수의 약수 중 공통된 것

예)

24, 18 - 1,2,3,6

최대 공약수란? 공통된 수 중 가장 큰 수

예)

24, 18 - 6

18/24 의 기약분수를 구할 때, 최대 공약수로 나누어야 하므로, 6을 구한 뒤 나누어 주는 작업을 수행하자

# 최대공약수 구하는 솔루션
def solution(a,b):
    g = 1
    for i in range(2,min(a,b)+1): # 두 수 중 최소까진 비교해봐야 한다.
        if a%i==0 and b%i==0:
            g = i
    return g


print(solution(18, 6))
print(solution(18, 24))
print(solution(33,12))

유클리드 호제법

GCD(a,b) = GCD(b,a%b)

# 재귀를 이용한 유클리드 호제법
def solution(a,b):
    if b==0:
        return a
    else:
        return solution(b,a%b)


print(solution(18, 6))
print(solution(18, 24))
print(solution(33,12))

# for 문을 이용한 호제법
def solution(a,b):
    while b != 0:
        r = a%b
        a = b
        b = r
    return a


print(solution(18, 6))
print(solution(18, 24))
print(solution(33,12))

3. 최소 공배수

24,18 - (24 * 18) / GCD(24,18)

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

def solution(A,B):
    while B != 0:
        r = A % B
        A = B
        B = r
    return A


def solution2(A,B):
    return (A*B) // solution(A,B)


A,B = map(int,input().split())
print(solution(A,B))
print(solution2(A,B))

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

n = int(input())

def gcd(a,b):
    while b != 0:
        r = a%b
        a = b
        b = r
    return a

for _ in range(n):
    arr = list(map(int,input().split()))
    k = arr.pop(0)
    sum = 0
    for i in range(k):
        for j in range(i+1,k):
            sum += gcd(arr[i],arr[j])
    print(sum)

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

n = int(input())

def gcd(a,b):
    while b != 0:
        r = a%b
        a = b
        b = r
    return a

for _ in range(n):
    arr = list(map(int,input().split()))
    a = arr[0]
    b = arr[1]
    g = gcd(a,b)
    lcm = (a*b)//g

    print(lcm)

4. 소수

약수가 1과 나 뿐인 수 = (2<= x <= N-1) 까지 나누어 떨어지면 안된다.

크게 두가지 유형

1. 어떤 수가 주어졌을 때, 소수인가? 예) 15는 소수인가?

# 2~n-1까지 숫자 돌리기
def solution(n):
    if n < 2:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True


print(solution(5))
print(solution(13))
print(solution(52))

# 2 ~ n//2 까지 숫자 돌리기
def solution(n):
    count = 0
    if n < 2:
        return False
    for i in range(2, n//2):
        count += 1
        if n % i == 0:
            return False
    print(count)
    return True


print(solution(5))
print(solution(97))

def solution(n):
    if n < 2:
        return False
    for i in range(2, n//2):
        if i**2 >= n:
            break
        if n % i == 0:
            return False
    return True


print(solution(5))
print(solution(98))

2. 1~100까지의 소수 전부를 구하자.

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

def prime(a,b):
    arr = []
    check = [False] * b
    for i in range(2,b):
        if check[i] == False:
            arr.append(i)
            for j in range(i*2,b,i):
                check[j] = True
    return arr



a,b = list(map(int,input().split()))
# a,b = 3, 16
arr= prime(a,b+1)
for i in arr:
    if a <= i <= b:
        print(i)

def isPrime(n):
    if n<2:
        return False
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            return False
    return True


def prime(a,b):
    for i in range(a,b):
        if isPrime(i):
            print(i)


a,b = list(map(int,input().split()))
# a,b = 3, 16
arr= prime(a,b+1)

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

def isPrime(n):
    if n<2:
        return False
    for i in range(2,int(n**0.5)+1):
        if n%i==0:
            return False
    return True


n = int(input())
arr = list(map(int,input().split()))
count = 0
for i in range(n):
    if isPrime(arr[i]):
        count += 1
print(count)

def isPrime(n):
    if n<2:
        return False
    i = 2
    while i**2 <= n:
        if n%i == 0 :
            return False
        i+=1
    return True


n = int(input())
arr = list(map(int,input().split()))
count = 0
for i in range(n):
    if isPrime(arr[i]):
        count += 1
print(count)

아리스토테네스의 체

2~<= NR까지 체로 다 걸러라.

def solution(a):
    arr = []
    check = [False] * a
    for i in range(2,a):
        if check[i] == False:
            arr.append(i)
            for j in range(i*2,a,i):
                check[j] = True
    return arr


print(solution(5))
print(solution(100))