01. 숫자

숫자

• 파이썬에서 정수는 int 이며 immutable 하다.
• 정수의 크기는 4Byte(32bit)이다.

최대공약수(GCD)

• 유클리드 호제법을 사용

  

최소공배수(LCM)

• 최대공약수를 이용하여 lcm을 구할 수 있다.
• gcd를 g라고 가정하면
• a = ga, b = gb 이다.(단, a, b은 서로소)
• lcm은 gab 이므로 lcm = a * b / gcd(a, b) 라고 할 수 있다.

피고나치 수열(Fibonacci sequence)

• 피고나치 수열(fibonacci sequence)은 첫째 및 둘째 항이 1이며, 그 이후의 모든 항은 바로 앞 두항의 합인 수열
• 1 1 2 3 5 8 13 21 ...
• find_fibonacci_seq_iter()의 시간복잡도는 O(n)을 갖는다.
• find_fibonacci_seq_rec()의 시간복잡도는 O(2^n)을 갖는다.
• find_fibonacci_seq_form()의 시간복잡도는 O(1)을 갖는다.(70번째 이상의 결과는 정확하지 않다.)

소수(Prime number)

• 소수란, 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수

• 즉, 약수로 1과 자기 자신만을 가지는 수

• (1) 무차별 대입 방법(brute force)

  • 이론적으로 가능한 모든 경우의 수를 다 검색해 보는 것

• (2) 제곱근을 이용한 방법

  • 판별해야 하는 수가 m 이라고 가정하자.
  • m이 소수가 아니면 m = a * b 인 합성수이다.(a, b, m은 자연수)
  • 따라서 min(a, b) 는 sqrt(m) 보다 작거나 같다.
  • 만약 m이 소수이면, 2 ~ (sqrt(m) + 1)으로 나눠져서는 안된다.
  • ex) 18 => (2, 9), (3, 6)
  • sqrt(18) = 4.24

• (3) 페르마의 소정리(Femat's little theorem)를 이용한 방법