---
title: 프로그래머 기초 수학 2-1 - 정수
tags:
  - algorithm
  - mathematics
published: true
mathjax: true
date: 2020-07-23 06:39:54
description: '정수'
category: programming
slug: /2020/07/math-for-programmer-chapter2-1-integer/
template: post
---

## Table of Contents

## 개념

- 정수: 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의 배수를 모두 지운다.
위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

```javascript
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
$$

로 표현될 수 있다.