백준 문제풀이 4948번 베르트랑 공준

2021/11/16 #algorithm #boj #silver #basic-math

[백준 문제풀이] 4948번 베르트랑 공준

4948번 베르트랑 공준 (Silver 2)

문제

https://www.acmicpc.net/problem/4948

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.

이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.

예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)

자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 케이스는 n을 포함하는 한 줄로 이루어져 있다.

입력의 마지막에는 0이 주어진다.

출력

각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.

풀이

반복문과 제곱근 나누기 방식의 에라토노스체로 접근했다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
const fs = require("fs");

const input = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((el) => el * 1);

const max = Math.max(...input);
let screen = Array.from({ length: max * 2 + 1 }, () => true);
screen[0] = false;
screen[1] = false;

for (let i = 2; i <= max * 2; i++) {
  if (screen[i]) {
    for (let j = 2; i * j <= max * 2; j++) {
      screen[i * j] = false;
    }
  }
}

let answer = Array.from({ length: input.length - 1 }, () => 0);
for (let i = 0; i < input.length - 1; i++) {
  for (let j = input[i] + 1; j <= input[i] * 2; j++) {
    if (screen[j]) answer[i] += 1;
  }
}

console.log(answer.join("\n"));
Read more

백준 문제풀이 1929번 소수 구하기

2021/11/15 #algorithm #boj #silver #basic-math

[백준 문제풀이] 1929번 소수 구하기

1929번 소수 구하기 (Silver 3)

문제

https://www.acmicpc.net/problem/1929

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

시간 제한 : 2초, 메모리 제한 : 256mb

첫 번째 풀이

이번이야말로 에라토스테네스의 체를 사용해야하나 싶었는데, 1,000,000까지 배수의 배열을 만드는 것이 비효율적일 것 같았다. 해서 제곱근까지의 곱을 비교하는 로직을 사용했다.

수가 커서 이전에 사용했던 직접 나누어서 계산하는 로직을 사용하면, 시간 초과가 생길 것 같았다.

직접 나누는 로직의 시간 복잡도는 O(N)이고, 제곱근까지의 수를 나누어서 계산하는 것은 O(√ N)로, 앞의 방법보다 빠르다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const fs = require("fs");
const [M, N] = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split(" ")
  .map((el) => el * 1);

let answer = "";
let screen = Array.from({ length: N + 1 }, () => true);
screen[0] = false;
screen[1] = false;

for (let i = 2; i <= Math.floor(Math.sqrt(N)); i++) {
  if (screen[i]) {
    for (let j = 2; i * j <= N; j++) {
      screen[i * j] = false;
    }
  }
}

for (let i = M; i <= N; i++) {
  if (screen[i]) answer += i + "\n";
}

console.log(answer);
Read more

백준 문제풀이 11653번 소인수분해

2021/11/15 #algorithm #boj #silver #basic-math

[백준 문제풀이] 11653번 소인수분해

11653번 소인수분해 (Silver 5)

문제

https://www.acmicpc.net/problem/11653

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

제한시간 : 1초

첫 번째 풀이

N이 10,000,000이하라서, 전부 일일이 나눠보는 것은 문제가 있다고 생각했다. 소인수분해라는 것은 결국 소수로 나눠지는 것이기 때문에, N까지의 소수를 먼저 구한 뒤 하나씩 나눠보는 방식이 맞다고 생각했다.

아니었다.

두 번째 풀이

작은 수부터 하나씩 나눠보면, 자연스럽게 소인수분해가 된다는 것을 알았다. 다만 나눠지지 않을때는 수를 하나씩 올리면서 실행해보았다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const fs = require("fs");

let input = parseInt(fs.readFileSync("/dev/stdin").toString().trim());
const primes = [];

let divider = 2;
while (input >= divider) {
  if (input % divider === 0) {
    input = input / divider;
    primes.push(divider);
  } else {
    divider++;
  }
}

console.log(primes.join("\n"));
Read more

백준 문제풀이 2581번 소수

2021/11/14 #algorithm #boj #silver #basic-math

[백준 문제풀이] 2581번 소수

2581번 소수 (Silver 5)

문제

https://www.acmicpc.net/problem/2581

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.

예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

출력

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.

단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

제한시간 : 1초

풀이

M과 N이 10,000 이하의 자연수라서, 에라토스테네스의 체를 사용해야하나 생각이 들었다. 문제는 메모리가 128mb 라는 것이었다.

그냥 나누기로 했더니 풀렸다. 자꾸 오류가 났었는데, 배열을 Boolean 값으로 검증하는 방식보다 배열의 길이가 0인지 검증하는 쪽이 더 정확하다는 것을 알게되었다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
const fs = require("fs");

const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const a = parseInt(input[0]);
const b = parseInt(input[1]);
const primeNumbers = [];
let sum = 0;

for (let i = a; i <= b; i++) {
  if (i === 2) {
    primeNumbers.push(i);
    sum += i;
  } else if (i !== 1) {
    let multiple = false;
    for (let l = 2; l < i; l++) {
      if (i % l === 0) {
        multiple = true;
      }
    }
    if (!multiple) {
      primeNumbers.push(i);
      sum += i;
    }
  }
}

if (!primeNumbers.length) {
  console.log(-1);
} else {
  const min = Math.min(...primeNumbers);
  console.log(sum);
  console.log(min);
}
Read more

백준 문제풀이 1978번 소수 찾기

2021/11/13 #algorithm #boj #silver #basic-math

[백준 문제풀이] 1978번 소수 찾기

1978번 소수 찾기 (Silver 4)

문제

https://www.acmicpc.net/problem/1978

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데, 수는 1000 이하의 자연수이다.

풀이 : 에라토스테네스의 체

소수를 구하는 공식이 있을 것 같아서 서치해보았고, 에라토스테네스의 체라는 것을 알게 되었다. 에라토스테네스의 체는 1이 아닌 수의 배수들을 제외한 값들을 소수로 판단하여 계산하는 것으로, 모든 수를 그 이하의 다른 수로 나누는 것보다 효율적이라고 한다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
const fs = require("fs");

const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const N = parseInt(input[0]);
const numbers = input[1].trim().split(" ");
const nonMultiples = [];

numbers.map((number) => {
  let multiple = false;

  if (parseInt(number) === 1) {
    multiple = true;
  }

  for (let l = 2; l < parseInt(number); l++) {
    if (parseInt(number) % l === 0) {
      multiple = true;
    }
  }

  if (parseInt(number) === 2) {
    nonMultiples.push(number);
  } else if (!multiple) {
    nonMultiples.push(number);
  }
});

if (numbers === []) {
  console.log(0);
} else {
  console.log(nonMultiples.length);
}
Read more