728x90

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

Code

Solution 1
Solution 2 개선된 코드

😢 '에라토스테네스의 체'를 이용해서(1929번 문제) 구간만 잘 정해주면 된다.

😊 Solution 1)
마지막에 0을 받으면 끝나도록 while loop을 돌려줬다.
1929번 문제에서 M, N을 여기서는 n = 입력 받은 값, m = n * 2로 구간을 설정해줬다.
또한, 값을 판단하기 위해 선언하는 Array에서, 구간을 벗어나는 index에 false를 세팅해주고 시작하면 된다.
(0보다 크고 n보다 작거나 같을 때까지)

추가 Solution 2) 코드 개선
전체 입력을 반복하는 반복문은 for ... of로 대체하였으며, 첫 째 줄에 0을 받으면 break하도록 설정하였다.
n보다 크고 2n보다 작거나 같아야 하므로, 구간은 n+1부터 2n까지라고 보면 된다. 
따라서 n=num+1, m=2*num으로 구간을 선언해주었다.
마찬가지로, m+1만큼 Array를 선언해준 후 fill(true)로 채워줬다. (index 0과 1은 false로 채워줬다)
이제 에라토스테네스의 체 방법으로 소수를 구해주고, n부터 m까지 소수가 있다면 count 후 counter를 출력해줬다.

이렇게 3396ms에서 520ms로 속도를 개선할 수 있었다.

Full Code (https://github.com/DasolPark/Dasol_JS_Algorithm/tree/master/Baekjoon)

// 베르트랑 공준(Bertrand Gongjoon)
 
// 2nd Solution
 
// For submit
 
// const fs = require('fs');
// const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n').map(num => parseInt(num));
 
// For local test
const input = [1, 10, 13, 100, 1000, 10000, 100000, 0];
for (let num of input) {
if (num === 0) {
break;
}
 
const n = num + 1;
const m = 2 * num;
const isPrimeNumArr = new Array(m + 1);
let counter = 0;
 
isPrimeNumArr.fill(true);
isPrimeNumArr[0] = isPrimeNumArr[1] = false;
 
for (let i = 2; i <= m; i++) {
if (Math.pow(i, 2) > 1000000) {
break;
} else {
for (let square = Math.pow(i, 2); square <= m; square += i) {
isPrimeNumArr[square] = false;
}
}
}
 
for (let i = n; i <= m; i++) {
if (isPrimeNumArr[i]) {
counter++;
}
}
console.log(counter);
}
 
// 1st Solution
 
// For submit
 
// const fs = require('fs');
// const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n').map(num => parseInt(num));
 
// For local test
// const input = [1, 10, 13, 100, 1000, 10000, 100000, 0];
 
// while (true) {
// const n = input.shift();
// if (n === 0) {
// break;
// }
// let counter = 0;
// const m = 2 * n;
// const isPrimeArr = new Array(m + 1);
 
// isPrimeArr.fill(true);
// for (let i = 0; i <= n; i++) {
// isPrimeArr[i] = false;
// }
 
// for (let i = 2; i < m + 1; i++) {
// if (parseInt(Math.pow(i, 2) > m)) {
// break;
// } else {
// for (let square = parseInt(Math.pow(i, 2)); square < m + 1; square += i) {
// isPrimeArr[square] = false;
// }
// }
// }
 
// for (let i = 2; i < m + 1; i++) {
// if (isPrimeArr[i]) {
// counter++;
// }
// }
// console.log(counter);
// }

+ Recent posts