2581번 소수

소수(0.1할때 그 소수아님) 를 구하는 문제. 대신 범위가 주어져서 생각보다 많은수를 구해야했다. 코딩을 처음 접했을때 풀어봤는데, 지금이랑 풀이가 사뭇 다르다.

const fs = require("fs");
const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");
const term = +input[1] - +input[0];
const arr = [];
const result = [];
const isPrime = (x) => {
  if (2 > x) return false;
  for (let i = 2; Math.sqrt(x) >= i; i++) {
    if (x % i === 0) return false;
  }
  return true;
};
if (term === 0) {
  if (isPrime(input[0])) result.push(input[0]);
} else {
  for (let i = 0; term >= i; i++) {
    arr[i] = +input[0] + i;
  }
  for (let i = 0; arr.length > i; i++) {
    if (isPrime(arr[i])) result.push(arr[i]);
  }
}
result.length > 0
  ? console.log(`${result.reduce((a, b) => a + b)}\n${result[0]}`)
  : console.log(-1);

vs

const fs = require("fs");
const input = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((el) => +el);
const [M, N] = input;
const stack = [];
for (let i = 2; i <= N; i++) {
  stack[i] = i;
}
for (let i = 2; i ** 2 <= N; i++) {
  if (stack[i]) {
    for (let j = i ** 2; j <= N; j += i) {
      stack[j] = 0;
    }
  }
}
const arr = stack.filter((el) => el >= M);
console.log(arr.length > 0 ? `${arr.reduce((a, b) => a + b)}\n${arr[0]}` : -1);

시간도 180ms vs 112ms로 압도적인 1.5배가량 차이난다. 두번째 풀이는 사실 에라토스테네스의 체라는 알고리즘기법을 이용했따.(검색함). 첫번째 풀이는 하나씩 소수판별을 하지만, 에라토스테네스의 체는 말 그대로 체처럼 소수가 아닌 숫자들을 걸러낸다.

에라토스테네스의 체

고대 그리스 수학자인 '에라토스테네스' 선생님께서 발명하신 소수찾기 기법이다. 역시 '고대' '그리스' '수학자'다. 무적의 삼위일체조합.

그래서 이녀석이 무엇인고 하니.

2부터(1은 아니니까) N까지의 소수를 판별할때 사용하는 알고리즘이다.
기법은 꽤 간단하다.

1. 2의 배수를 지운다.
2. 3의 배수를 지운다.
3. 5의 배수를 지운다.
4. 7의 배수를 지운다.
5. ...의 배수를 지운다. (소수의 배수)

단, 자기자신을 제외한다.

이렇게 반복해서 소수 자신을 제외한 배수를 제거하다보면 종국에 소수만 남게된다.
이것이 에라토스 테네스의 체.

그림으로 보면 더 쉽다.

출처 : https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4 킹갓 위키피디아

코드로 나타내면 이렇다.

//...N길이의 배열을 선언함.

//배열을 자연수로 채운다.
for (let i = 2; i <= N; i++) {
  stack[i] = i;
}

//N의 제곱근 까지 배수를 순회하면 된다.
for (let i = 2; i ** 2 <= N; i++) {
  //배수가 지워지지 않은 숫자라면.
  if (stack[i]) {
    //이부분이 핵심이다. j의 시작값을 i의 제곱(4)으로 두고, 배수를 지워나간다. 처음엔 코드가 잘 이해안됐음.ㅜㅜ
    // 4,6,8,10... / 9,12,15... / 25,30,35... 이런식.
    for (let j = i ** 2; j <= N; j += i) {
      stack[j] = 0;
    }
  }
}

11653번 소인수분해

소수로 인수분해를 하는 소인수분해. 작은수부터 분해해보면 된다.
처음엔 에라토스테네스의 체를 풀고난 뒤라, 이렇게 했다.

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim();
const N = +input;
if (N === 1) return;
const stack = [];
for (let i = 2; i <= N; i++) {
  stack[i] = i;
}
for (let i = 2; i ** 2 <= N; i++) {
  //소수를 찾는다.
  if (stack[i]) {
    for (let j = i ** 2; j <= N; j += i) {
      stack[j] = 0;
    }
  }
}
const arr = stack.filter((el) => el !== 0);
let quotient = N;
let index = 0;
while (true) {
  if (arr[index] > quotient) break;
  if (quotient % arr[index] === 0) {
    console.log(arr[index]);
    quotient = quotient / arr[index];
  } else index++;
}

1부터 n까지 하릴없이 소수를 찾아낸 후, 인수분해를 돌렸다.

그 충격적인 결과는 856ms.
속도가 느려도 너무느렸다. 생각해보면, 굳이 모든 소수를 찾을 필요는 없어보였다.

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim();
const N = +input;
if (N === 1) return;
let quotient = N;
let i = 2;
while (true) {
  if (quotient === 1) break;
  if (quotient % i === 0) {
    console.log(i);
    quotient = quotient / i;
    i = 2;
  } else i++;
}

첫번째로 나뉘어지는 수는 소수다. 직관적으로 이해되진 않았지만 추측에 기반해 돌려본 알고리즘이다. 놀랍게도 결과는 성공. 가만 생각해보면
1. 2로 나뉘면 짝수로는 나뉘질 않는다.
2. 3으로 나뉘면 3의배수는 안나뉨.
3. 5로 나뉘면...
4. 7로...

어라 이거 에라토스테네스의 체랑 비슷한것 같은데...?
소수를 구하는거라 그런지, 원리는 비슷하구만!