All Articles

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

개념

  • 정수: 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))
    }

    어떤수 로 소인수 분해 할 수 있다면, 의 약수는 총 개 다.

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

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

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

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

따라서 최소 공배수 L은

로 표현될 수 있다.