자바스크립트로 알고리즘 정리하기 #7 수학2 (소수, 팩토리얼)

자바스크립트로 알고리즘 정리하기 #7 수학 (소수, 팩토리얼)

소수

• 약수가 1과 자기 자신밖에 없는 수
• N이 소수가 되려면 2보다 크거나 같고 N보다 작은 자연수로 나누어 떨어지면 안된다.
• 1부터 100까지의 소수는?
  • 2, 3, 5, 7, 11, 13, 17 ...

소수와 관련된 알고리즘

1. 어떤 수 N이 소수인지 아닌지 판별하는 방법
2. N보다 작거나 같은 모든 자연수 중에서 소수를 찾아내는 방법

어떤 수 N이 소수인지 아닌지 판별하는 방법

정의를 그대로 이용해서
1. N이 2보다 크거나 같은지 확인하고,
2. 2부터 N-1까지 반복하며 나누어 떨어지는지 확인한다.

• 사실 N-1까지 안해도 N/2을 넘어서는 수로는 나눠떨어지지 않는 다는 것을 생각하면 N/2까지만 나누어 떨어지는지 확인해보아도 충분하다.
• 약수 중에서 가장 큰것은 N/2보다 작거나 같기 때문이다.

let isPrimeNumber = n => {

    if(n < 2) {
        return false;
    }

    for(let i=2; i<=n/2; i++){
        if(n % i === 0){
            return false;
        }        
    }

    return true;
}

소수를 구하는 코드를 위와 같이 구현할 수 있다.

어떤 수 N이 소수인지 아닌지 판별하는 방법(확장)

• N이 소수가 아니라면 N은 a*b의 형식으로 표현 가능하다.
• N이 소수가 아닐 때, N이 a*b로 표현 된다면, 소수라면 같은 수의 곱으로 이루어지진 않으니까 a와 b의 관계식을 a <= b로 표현할 수 있다.
• 만일 a > b 라면 두 수를 바꿔서 항상 a <= b로 표현이 가능하다.
  • 여기서 a와 b의 차이가 최소로 날 때 그 값이 얼마인지 구해보자.
    • 루트 n * 루트 n은 n이 나온다.
    • n이 a*b로 표현될 수 있고, a <= b 일 때, b의 최소 값이며 a의 최대 값은 루트 n이다.
      • 왜냐하면 a가 루트 n보다 크게 되면, a*b > n이 되어버린다.
      • 반면에 b가 루트 n보다 작게 되면, a*b < n이 되어버린다.
    • a<=b 일 때, a <= 루트 n, b >= 루트 n이다.
    • a < 루트 n, b < 루트 n 이면, a*b < n이 된다.
    • a > 루트 n, b > 루트 n 이면, a*b > n이 된다.
      • a와 b의 차이가 가장 작은 경우는 a와 b가 서로 루트 n이 되는 경우이다.
        • 그러므로 루트 n까지만 반복해보면 이 수가 소수인지 알 수 있다.

let isPrimeNumber = n => {
    if (n < 2) { 
        return false;
    }
	// i<=Math.sqrt(n) 대신 i*i <= n 이 더 바람직한 코드이다.
    // 실수를 사용하는 것은 바람직하지 않기 때문.
    for(let i=2; i<=Math.sqrt(n); i++){
        if(n % i === 0){
            return false;
        }
    }

    return true;
}

위와 같은 코드로 구성하면 시간복잡도가 훨씬 빠르게(O(루트n)) 소수를 구할 수 있다.

큰 수의 경우에는 이 효과가 훨씬 크다.

boj 1978 소수 구하기

문제 링크

let isPrimeNumber = (n) => {
  if (n < 2) {
    return false;
  }

  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (n % i === 0) {
      return false;
    }
  }

  return true;
};

let solution = (input) => input[1].split(' ').filter((n) => isPrimeNumber(n)).length;

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

rl.on('line', function (line) {
  input.push(line);
}).on('close', function () {
  console.log(solution(input));
  process.exit();
});

범위의 소수를 구하기

범위의 소수를 구한다는 것은 이를테면 1~100000까지의 소수를 구하는 것과 같다.

이 경우에는 이전에 배웠던 O(루트n)의 방법을 반복하지 않고, 에라토스테네스의 체 라는 더 빠른 방법을 이용한다.

에라토스테네스의 체

1부터 N까지의 모든 소수를 구할 때 쓴다.

1. 2부터 N까지 모든 수를 써놓는다.
2. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.
3. 그 수는 소수이다.
4. 그 수의 배수를 모두 지운다.
5. N이 최대값이기 때문에 루트 N보다 작거나 같은 수의 배수를 모두 지우면 끝난다.

• 어떤 수 N이 소수인지 아닌지 판별하는 방법(확장) 에서 배웠던 방법을 참조하자.

에라토스테네스의 체 구현

let era = n => {
    // it gets all prime numbers from 2 to n
    let sieve = new Array(n+1).fill(true);

    sieve[0] = false;
    sieve[1] = false;
    
    for(let i=2; i*i<=n; i++){
        if(sieve[i]){
          // j=i*i를 해도 무관하지만,
          // 범위가 100만인 경우에는 i*i가 1조가 되어 숫자의 범위를 초과할 수 있다.
          for(let j=i+i; j<=n; j+=i){
              sieve[j] = false;
          }
        }
    }

    return sieve.reduce((acc, cur, idx) => cur ? acc.concat(idx) : acc, []);
}

배열을 생성하고 그 배열의 인덱스 번호를 이용하여 구현해보았다.

에라토스테네스의 체보다 빠른 범위 내의 소수 구하는 방법

모든 소수는 6n+1과 6n+5로 이루어진다는 것을 이용하면 에라토스테네스의 체보다 더 빠르게 소수를 구할 수 있다.

• 6n은 2의 배수
• 6n+1은 소수
• 6n+2는 2의 배수
• 6n+3은 3의 배수
• 6n+4도 2의 배수
• 6n+5는 소수

위는 소수가 될 수 있는 범위이고 위의 범위를 한정하여 소수를 구하면 에라토스테네스의 체보다 조금 더 빠르게 소수를 구할 수 있다.

범위를 지정할 뿐, 완벽히 소수를 구해주는 것이 아님을 알자.

골드바흐의 추측 (boj 6588)

• 추측 내용
  • 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다
  • 5보다 큰 모든 홀수는 세 소수의 합으로 표현 가능하다
• 아직 증명되지 않은 추측
  • 10의 18제곱 이하에서는 참인 것이 증명되었다
• 문제의 내용은 100만까지의 숫자가 소수로 표현될 수 있는지 검증하라.

문제 링크

정답 코드

let era = (n) => {
  let range = new Array(n + 1).fill(true);
  range[0] = false;
  range[1] = false;

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

  return range;
};

let erathos = era(1000000);

let goldBach = (n) => {
  for (let i = 3; i < erathos.length; i++) {
    if (i > n) {
      break;
    }

    if (erathos[i]) {
      if (erathos[n - i]) {
        return `${n} = ${i} + ${n - i}`;
      }
    }
  }

  return "Goldbach's conjecture is wrong.";
};

let solution = (input) => {
  let answer = [];

  for (i = 0; i < input.length - 1; i++) {
    answer.push(goldBach(+input[i]));
  }

  return answer.join('\n');
};

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

rl.on('line', function (line) {
  input.push(line);
}).on('close', function () {
  console.log(solution(input));
  process.exit();
});

핵심은 에라토스테네스의 체로 100만까지의 소수의 목록을 구하면 소수의 인덱스만 true인 배열이 나온다. n-해당 소수의 인덱스가 true라면 소수로 그 수를 만들 수 있다는 것이다. 처음에는 O(소수의 배열 크기 * 소수의 배열 크기)의 형식으로 구했는데, 나중에 O(소수의 배열 크기) 로 최적화하였다.

node.js로 푼 사람 중 맞은 사람들을 체크해보니 대부분은 최적화를 하지 않은듯 하다. 속도가 느리다.

팩토리얼

• N! = 1 2 3 ... N-1 * N
• 매우 큰 값이 나온다.
• 브루트 포스 알고리즘을 풀 때 매우 중요하다.

팩토리얼 끝에서 연속된 0의 개수 (boj 1676)

문제 링크

• N!을 했을 때, 맨뒤에 0이 몇번 나오는지 알아내면 된다.
• 10!의 경우 3628800 이고 0은 2번 나온다.
• 범위가 0<=N<=500이기 때문에 팩토리얼을 직접 계산하면 매우 오래걸린다.
• 소인수분해로 알 수 있다.
  • 0을 만들 수 있는 방법은 2x5 외엔 없다는 것이 힌트.
  • 10! = 1*2*3*4*5*6*7*8*9*10 = 2의 6제곱 * 3의 4제곱 * 7 * 10의 2제곱
  • N!을 소인수분해 했을 때, 2와 5가 몇개 나오는지 알아야 한다.
  • 5의 개수가 항상 2의 개수보다 적기 때문에, 5의 개수만 세어주면 된다.
    • 5의 개수보다 많은 2가 있기 때문에 모든 5는 10처럼 0이 나오는 숫자가 된다. 그래서 5의 개수만큼 0이 나온다.
  • N!의 0의 개수 = [N/5] + [N/5의 제곱] + [N/5의 3제곱] + ...

let solution = (n) => {
  let answer = 0;

  answer += parseInt(n / +5);
  answer += parseInt(n / +25);
  answer += parseInt(n / +125);

  return answer;
};

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on('line', function (line) {
  console.log(solution(+line));
  rl.close();
}).on('close', function () {
  process.exit();
});

N의 최대값이 500이니까 5 25 125를 나눠서 나오는 몫만 구하면 된다.

자바스크립트는 따로 숫자에 int, float, double같은 형이 없으니 parseInt로 자료형을 고정하였다.

조합 0의 개수 (boj 2004)

문제 링크

위 문제의 응용이라고 보면 된다.

조합 공식을 보고 풀면 된다.

n! / r! (n - r)! 이게 조합 공식인데, 이걸 소인수분해 했을 때, 2와 5가 얼만큼 들어가는지 확인한 뒤에 지수법칙에 의거해서 값을 구해주면 된다.

위에서 팩토리얼에 2와 5가 얼마나 들어가는지 보았는데, 그걸 응용하면 된다.

단, 일반적인 팩토리얼의 경우 무조건 2가 더 많이 들어갔지만, 이 경우에는 5가 더 많이 들어갈 수도 있다.

n!의 2, 5의 갯수 - r!의 2, 5의 갯수 - (n - r)!의 2, 5의 갯수 대략 이러한 식이 완성될 것이다.

만약에 n!에서 5의 갯수가 1개가 나오고 2의 갯수가 2개가 나왔다고 쳐보자.
그런데 r!에서 2의 갯수가 1개가 나오고 (n - r)!에서 2의 갯수가 1개 나온다면?

소인수 5만 남아 0을 생성할 수 없게 된다. 기본적으로 5와 2가 만나야 0이 생긴다.

실제로 위와 같은 케이스는 입력에 5와 1을 주었을 때 생긴다.

n!에서 5의 갯수가 1개가 나오고 2의 갯수가 3개가 나온다.
r!에서 5의 갯수가 0개가 나오고 2의 갯수가 0개가 나온다.
(n-r)!에서 5의 갯수가 0개가 나오고 2의 갯수가 3개가 나온다.

결국엔? 5만 남아 0을 만들 수 없게 된다.

정답 코드는 다음과 같다.

let solution = ([n, m]) => {
  // 팩토리얼은 무조건 2의 개수보다 5의 개수가 더 많았는데,
  // 조합은 2의 개수가 더 많을 수도 있으니 둘 다 세어야 한다.

  let five = new Array(3).fill(0);
  let two = new Array(3).fill(0);

  for (let i = 5; i <= n; i *= 5) {
    five[0] += parseInt(n / i);
  }

  for (let i = 5; i <= m; i *= 5) {
    five[1] += parseInt(m / i);
  }

  for (let i = 5; i <= n - m; i *= 5) {
    five[2] += parseInt((n - m) / i);
  }

  for (let i = 2; i <= n; i *= 2) {
    two[0] += parseInt(n / i);
  }

  for (let i = 2; i <= m; i *= 2) {
    two[1] += parseInt(m / i);
  }

  for (let i = 2; i <= n - m; i *= 2) {
    two[2] += parseInt((n - m) / i);
  }

  // 따로따로 계산하고 Math.min()을 수행했다가 틀렸었다.
  // 2와 5의 개수를 세려면 n과 m을 한번에 받은 뒤에 세어야 한다.
  // 왜냐하면 결국 지수의 마지막 결과를 구해야 하기 때문
  // 이전 팩토리얼을 풀던 것과 개념을 헷갈리면 안된다.
  return Math.min(five[0] - (five[1] + five[2]), two[0] - (two[1] + two[2]));
};

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on('line', function (line) {
  console.log(solution(line.split(' ').map((e) => +e)));
  // 지수가 있는 수끼리 나누면 지수법칙에 의해 뺄셈이 된다는 성질 이용
  rl.close();
}).on('close', function () {
  process.exit();
});