프로그래머 기초 수학 2-1

개념

개념

정수: 1, 2, 3과 같은 자연수, 없음을 나타내는 0, 그리고 자연수와 반대 부호인 수 (-1, -2, -3...)
배수: 어떤 정수에 다른 정수를 곱하여 만들어진 정수 (15는 3과 5의 배수)
약수: 어떤 정수를 나머지 없이 나눌 수 있는 수
소수: 자기 자신과 1외에는 다른 약수가 없는 수
합성수: 1과 자기 자신외의 약수가 있어서 그 약수의 곱으로 나타낼 수 있는 수
- 1보다 큰 모든 정수는 소수이거나, 합성수 이다.
소인수분해: 소수인 약수들의 곱셉 형태로 합성수를 나타내는 것

72 = 8 \times 9 = (2 \times 2 \times 2) \times (3 \times 3) = 2^3 \times 3^2

소인수 분해는 고성능 컴퓨터로도 오래걸리며, 현대 암호학은 소수의 성질에 의존하고 있다. 소수를 골라 낼 때는 에라토스테네스의 체를 사용한다.

에라토스테네스의 체

2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색) 자기 자신을 제외한 2의 배수를 모두 지운다. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색) 자기 자신을 제외한 3의 배수를 모두 지운다. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색) 자기 자신을 제외한 5의 배수를 모두 지운다. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색) 자기 자신을 제외한 7의 배수를 모두 지운다. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

function solution(n) {
  const arr = new Array(n).fill(true)

  for (let i = 2; i * i <= n; i += 1) {
    if (arr[i]) {
      for (let j = i * i; j <= n; j += i) {
        arr[j] = false
      }
    }
  }

  arr.splice(0, 2, false, false)

  return arr
    .map((value, index) => (value ? index : false))
    .filter((value) => Boolean(value))
}

어떤수 $N$ 이 $a^m \times a^b$ 로 소인수 분해 할 수 있다면, $N$ 의 약수는 총 $(m+1) \times (n+1)$ 개 다.

공약수: 두 수의 약수 중에 공통되는 것
최대 공약수: 공약 수 중 가장 큰 수
서로소: 1외에 공약수가 없는수
공배수: 두 수의 배수 중에서 공통 된 것
최소공배수: 공배수 중 가장 작은 것

두 수 A와 B, 그리고 이들의 최대공약수를 G라고 하고, 최대공약수에 속하지 않는 약수들의 곱을 a, b라고 하자. a, b는 최대 공약수의 정의에 따라 서로소 일 것이다..

A = G \times a B = G \times b

A, B의 배수들을 구하면 다음과 같은 모양이 될 것이다.

A : (G \times a) \times (1, 2, 3 ... ) B : (G \times b) \times (1, 2, 3 ... )

여기서 최소공배수를 구해보자.

A: (G \times a) \times b B: (G \times b) \times a

따라서 최소 공배수 L은

L = G \times a \times b

로 표현될 수 있다.

프로그래머 기초 수학 2-1 - 정수

Table of Contents

개념