출처: 백준 온라인저지
https://www.acmicpc.net/problem/1929
1929번: 소수 구하기
첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.
www.acmicpc.net
답안 ( 오답 - 시간 초과)
const input = require('fs')
.readFileSync('/dev/stdin')
.toString()
.trim()
.split(' ');
const m = +input[0];
const n = +input[1];
let answer = '';
for (let i = m; i <= n; i++) {
for (let j = 2; j <= i; j++) {
if (i < 2) {
break;
}
if (i % j === 0 && i === j) {
answer += j + '\n';
} else if (i % j === 0 && i !== j) {
break;
}
}
}
console.log(answer);
1. 반복문을 사용하여 m과 n 사이의 숫자들을 구한다.
2. 구한 숫자들을 또 다시 2부터 반복문을 돌리면서 소수를 찾아서 answer 변수에 추가한다.
=> 이 로직을 따를 경우, 반드시 2번의 반복문을 중첩해야하며 2번 모두 처음부터 끝까지 모든 경우의 수에 대해 반복문이 끝나야하므로
2초인 시간 제한을 맞출 수 없다.
=> 앞선 베트르랑 공준과 마찬가지로 에라토스테네스의 체를 참고하여 Math.sqrt 함수를 사용하여 소수를 찾음으로써 로직을 간단하게 해야한다.
두번째 답안(오답)
const input = require('fs')
.readFileSync('/dev/stdin')
.toString()
.trim()
.split(' ');
const m = +input[0];
const n = +input[1];
let answer = '';
for (let i = m; i <= n; i++) {
for (let j = 2; j <= Math.ceil(Math.sqrt(i)); j++) {
if (i <= 1) {
break;
}
if (i % j === 0) {
break;
}
if (i % j !== 0 && j === Math.ceil(Math.sqrt(i))) {
answer += i + '\n';
}
}
}
console.log(answer);
1. 반복문을 사용하여 m과 n 사이의 숫자들을 구한다.
2. 구한 숫자들을(변수 i) 반복문을 사용하여 소수인지 체크를 하는데, 이때 사용될 변수 j는 에라토스테네스의 체를 활용하여 Math.sqrt(i) 보다 작은 수들이다. 단, 이때 숫자가 3일 경우 Math.sqrt(i) 의 값은 1.7xxx 로 2로 시작하는 j 값보다 작기 때문에 Math.ceil 을 사용한다.
3. 숫자가 1보다 작을 경우 즉, 0과 1은 소수가 아니므로 반복문을 나가도록 하고,
4. i % j 가 0인 경우도 소수가 아니므로 반복문을 나가도록 하고.
5. i % j 가 0이 아니고, j가 Math.ceil(Math.sqrt(i))) 경우 소수이므로 answer에 추가하도록 한다.
=> 아마도 Math.ceil(Math.sqrt(i)) 로 반올림 했을 때, i % j !== 0 && j === Math.ceil(Math.sqrt(i)) 조건에 어긋나는 반례가 존재하는 것 같다.
세 번째 답안 ( 정답 ✅ )
const input = require('fs')
.readFileSync('/dev/stdin')
.toString()
.trim()
.split(' ');
const n = +input[0];
const m = +input[1];
let isPrimeNum = Array(m + 1).fill(true);
isPrimeNum[0] = isPrimeNum[1] = false;
answer = '';
function getPrimeNum() {
for (let i = 2; i <= Math.ceil(Math.sqrt(m)); i++) {
if (isPrimeNum[i]) {
let multiple = 2;
while (i * multiple <= m) {
isPrimeNum[i * multiple] = false;
multiple++;
}
}
}
for (let i = n; i <= m; i++) {
if (isPrimeNum[i]) {
answer += i + '\n';
}
}
console.log(answer);
}
getPrimeNum();
다른 사람 답안
JavaScript 백준 1929번 소수구하기
🔥백준 1929 소수구하기 >https://www.acmicpc.net/problem/1929 🧵풀이 공부하는 중이라 글이 깔끔하지 못하거나 틀린부분이 있을 수 있습니다. 더 좋은 방법이 있거나 부족한 부분이 존재한다면 말씀해
velog.io
[JS] 백준 1929번 소수 구하기
출처 백준 온라인 저지 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는..
gurtn.tistory.com
'알고리즘' 카테고리의 다른 글
프로그래머스 JS | 모의고사 (완전탐색) (0) | 2022.06.25 |
---|---|
백준 JS | 17478번 재귀함수가 뭔가요? (0) | 2022.06.21 |
백준 JS | 4948번 베르트랑 공준 (0) | 2022.06.10 |
백준 JS | 2775번 부녀회장이 될테야 (0) | 2022.05.26 |
백준 JS | 1316번 그룹단어 체커 (0) | 2022.05.17 |