기본 정수론

정수론(Number theory)

• 정수의 성질을 연구하는 분야

정수(Integer)
-90 -3 0 1 5 8 10 14 15 19

 

약수(Divisor)

• 특정 정수를 나누어 떨어지게 하는 수

20의 약수
-> 1, 2, 4, 5, 10, 20

#구현

import sys
 
if __name__ == "__main__":
  input = sys.stdin.readline
  
  n = int(input())
  
  for i in range(1, n+1):
    # 숫자 i가 n의 약수인지 판단
    if n%i == 0:
      print(i, end=' ')
  

 

소수(Prime number)

• 약수가 1과 자기 자신뿐인 정수

7의 소수
-> 1, 7

#구현

import sys
 
 
if __name__ == "__main__":
  input = sys.stdin.readline
  n       = int(input())
  isPrime = True
  
  for i in range(2,  n):
    if n%i == 0:
      isPrime = False
      break
    
  if isPrime:
    print('YES')
  else:
    print('NO')

 

에라토스테네스의 체

• 소수를 구하는 방법 중 하나
• 배수를 제거하면서 소수를 구하는 방식

1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50

-> 1을 제외한 가장 작은 수 2를 선택 후 2는 소수라고 판정.
-> 2의 배수들은 모두 소수가 될 수 없으므로 제외
-> 그 다음 작은 수 3을 선택
-> 3의 배수들을 모두 소수가 될 수 없으므로 제외
-> 그 다음 작은 수 5를 선택
-> 5의 배수들을 모두 소수가 될 수 없으므로 제외
. . .

**시간복잡도 : nlogn => 빠르다
- 1~n까지의 자연수 중 모든 소수를 구할 때 적합
- n이 소수인지를 판단할 때는 부적합

예제 : https://ttolkist.tistory.com/257

chebyshevtheo

소인수 분해(Prime factorization)

• 숫자 N을 소수의 곱으로 나타냄

60
-> 2^2, 3, 5

#구현

import sys
 
if __name__ == "__main__":
  input = sys.stdin.readline
  n = int(input())
  
  idx = 2
  while n>1:
    if n%idx == 0:
      print(idx, end=' ')
      n //= idx
    else:
      idx += 1

 

공약수와 공배수

• A와 B의 공약수 : A의 약수이면서 동시에 B의 약수인 수

8 36
-> 1, 2, 4

• A와 B의 공배수 : A의 배수이면서 동시에 B의 배수인 수

8 36
-> 72, 144, ...

 

최대공약수와 최소공배수(Greatest Common Divisor and Lower Common Multiplier)

• A와 B의 최대공약수(GCD) : A의 약수이면서 동시에 B의 약수인 수 중 최댓값

8 36
-> 4

• A와 B의 최소공배수(LCM) : A의 배수이면서 동시에 B의 배수인 수 중 최솟값

8 36
-> 72

 

유클리드 호제법

• 최대공약수를 구하기 위한 알고리즘

152 68 의 최대 공약수를 구하는 원리.

a           b         r(a를 b로 나눈 나머지) 
152       68        20
68         20        8
20          8         4
8            4         0
=> 4가 최대 공약수이다.

#구현

import sys 
# 158 86 => 최대 공약수 출력
 
if __name__ == "__main__":
  input = sys.stdin.readline
  a, b  = map(int, input().split())
  origin_A, origin_B = a, b
  GCD   = 0
  LCM   = 0
  while True:
    r = a % b
    if r == 0:
      GCD = b 
      break
    a = b
    b = r
    
  LCM = (origin_A//GCD)*(origin_B//GCD)*GCD
  print(GCD) #최대공약수
  print(LCM) #최소공배수