IT&컴퓨터/프로그래밍

파이썬으로 수학연산(나머지,최대공약수,최소공배수,소수)

백단z 2021. 12. 1. 19:49

기회가 될 때마다 파이썬 공부를 하려고 한다.

공부해서 글로 남겨놓고 복습하면서 암기하자~~~

나머지 연산

(A+B)%C는 ((A%C) + (B%C))%C 같다.

(A×B)%C는 ((A%C) × (B%C))%C 같다.

​

최대공약수(Greatest Common Divisor : GCD)

두 수의 최대공약수는 두 수의 약수 중에서 가장 큰 정수이다.

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

  18 : 1,2,3,6,9,18

  공약수 : 1,2,3,6

  최대공약수 : 6

​

GCD는 유클리드 호제법(Euclidean algorithm)을 이용하면 빠르게 구할 수 있다.

  GCD(a,b) = GCD(b,r) #r은 a, b 를 나눈 나머지

  r이 0이면 그 때의 b가 GCD이다.

​

  GCD(24,16) = GCD(16,8) = GCD(8,0) = 8

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)
세 수의 최대공약수 : GCD(GCD(a,b),c)

N 수의 최대 공약수 : GCD(GCD(N~~~ ???

최소공배수(Least Common Multiple : LCM)

두 수의 최소공배수는 두 수에 서로 공통으로 존재하는 배수이다.

  8 : 8, 16, 24, 32, 40, 48, 56, 64, 72, 80, ...

  10 : 10, 20, 30, 40, 50, 60, 70, 80, ...

  공배수 : 40, 80, ...

  최소공배수 : 40

​

최소공배수는 최대공약수를 이용하여 계산할 수 있다.

  LCM = a*b//GCD #파이썬에서 // 연산자는 소수점을 버린 몫만을 취함.

​

GCD 합

특별히 설명할게 있나.................. 말 그대로 최대공약수의 합을 계산해보자.

a = list(map(int, input().split()))
n = a[0]
a = a[1:]
ans = 0
for i in range(0, n-1):
    for j in range(i+1, n):
        ans += gcd(a[i], a[j])
print(ans)

​

소수(Prime Number)

소수는 약수가 1과 자기 자신 밖에 없는 수(2,3,5,7,11,13,17, ...)

​

에라토스테네스의 체(Sieve of Eratosthenes)를 이용하면 소수를 빠르게 찾을 수 있다.

  1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.

  2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)

  3. 자기 자신을 제외한 2의 배수를 모두 지운다.

  4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)

  5. 자기 자신을 제외한 3의 배수를 모두 지운다.

  6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)

  7. 자기 자신을 제외한 5의 배수를 모두 지운다.

  8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)

  9. 자기 자신을 제외한 7의 배수를 모두 지운다.

  10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]
반응형