소수 구하기 - 에라토스테네스의 체
두 수 n과 m이 주어질 때, n이상 m이하의 모든 소수를 출력하라.
// const fs = require("fs");
// const filePath = process.platform === "linux" ? "dev/stdin" : "input.txt";
// const stdin = fs.readFileSync(filePath).toString().split("\n");
// let cnt = 0;
// const input = () => {
// return stdin[cnt++];
// };
const solution = () => {
const [m, n] = input()
.split(" ")
.map((x) => parseInt(x));
const arr = new Array(n + 1).fill(1, 2, n + 1);
for (let i = 2; i <= n; i++) {
if (arr[i]) {
for (let j = i * i; j <= n; j += i) {
arr[j] = 0;
}
}
}
const result = [];
for (let i = m; i <= n; i++) {
if (arr[i]) {
result.push(i);
}
}
console.log(result.join("\n"));
};
// solution();
for (let i = 2; i <= n; i++) {
if (arr[i]) {
for (let j = i * i; j <= n; j += i) {
arr[j] = 0;
}
}
}
j = i * i
로 가령 i == 3
인 경우는 j = 9
부터 시작하기 때문에 계산량을 줄일 수 있다.