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

Table of Contents

• 개념

개념

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

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

• 에라토스테네스의 체

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, B의 배수들을 구하면 다음과 같은 모양이 될 것이다.

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

따라서 최소 공배수 L은

로 표현될 수 있다.