๋ชฉ์ฐจ
์๋ผํ ์คํ ๋ค์ค์ ์ฒด: ์ํ๊ณผ ์ปดํจํฐ ๊ณผํ์์์ ์ค์์ฑ
์ํ๊ณผ ๊ณ ๋ ์ญ์ฌ์์์ ์๋ผํ ์คํ ๋ค์ค์ ์ฒด
์๋ผํ ์คํ ๋ค์ค์ ์ฒด๋ ๊ณ ๋ ๊ทธ๋ฆฌ์ค ์ํ์ ์๋ผํ ์คํ ๋ค์ค๊ฐ ๋ฐ๊ฒฌํ ์์๋ฅผ ์ฐพ๋ ๋ฐฉ๋ฒ์ผ๋ก, ๊ฐ๋จํ๋ฉด์๋ ํจ์จ์ ์ธ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ์๋ ค์ ธ ์์ต๋๋ค. ์ด ๋ฐฉ๋ฒ์ ์ ํด์ง ๋ฒ์ ์์ ๋ชจ๋ ์์๋ฅผ ์ฐพ๊ธฐ ์ํด, 2๋ถํฐ ์์ํ์ฌ ๊ทธ ๋ฐฐ์๋ฅผ ์ง์๋๊ฐ๋ ๊ณผ์ ์ ๋ฐ๋ณตํ๋ ๊ฒ์ ๋๋ค. ์๋ฅผ ๋ค์ด, 2์ ๋ฐฐ์๋ฅผ ๋ชจ๋ ์ง์ฐ๊ณ , ๋ค์์ผ๋ก ๋จ์ ๊ฐ์ฅ ์์ ์์ธ 3์ ๋ฐฐ์๋ฅผ ์ง์๋๋ค. ์ด๋ฌํ ๊ณผ์ ์ ๋ฐ๋ณตํ๋ฉด ๊ฒฐ๊ตญ ๋จ๋ ์๋ค์ด ๋ฐ๋ก ์์๊ฐ ๋ฉ๋๋ค.
์ด ์๊ณ ๋ฆฌ์ฆ์ ๋จ์ํจ์๋ ๋ถ๊ตฌํ๊ณ ๋งค์ฐ ์ค์ํ ์๋ฏธ๋ฅผ ๊ฐ์ง๋๋ค. ์์๋ ์ํ์ ๋ค์ํ ๋ถ์ผ๋ฟ๋ง ์๋๋ผ ์ํธํ์์๋ ๋งค์ฐ ์ค์ํ ์ญํ ์ ํฉ๋๋ค. ๋ฐ๋ผ์, ํจ์จ์ ์ผ๋ก ์์๋ฅผ ์ฐพ๋ ๋ฐฉ๋ฒ์ ๊ณ ๋๋ถํฐ ํ๋์ ์ด๋ฅด๊ธฐ๊น์ง ์ฌ๋ฌ ๋ถ์ผ์์ ์์ฉ๋ฉ๋๋ค.
์ปดํจํฐ ๊ณผํ์์์ ์๋ผํ ์คํ ๋ค์ค์ ์ฒด์ ์์ฉ
์ปดํจํฐ ๊ณผํ์์ ์๋ผํ ์คํ ๋ค์ค์ ์ฒด๋ ์๊ณ ๋ฆฌ์ฆ์ ๊ธฐ์ด์ ์ธ ์์๋ก ์์ฃผ ์ฌ์ฉ๋ฉ๋๋ค. ํนํ, ํ๋ก๊ทธ๋๋ฐ์ ๋ฐฐ์ฐ๋ ํ์๋ค์๊ฒ ๋ฐ๋ณต๋ฌธ๊ณผ ์กฐ๊ฑด๋ฌธ์ ์ฌ์ฉ์ ๊ฐ๋ฅด์น๋๋ฐ ์ ์ฉํ๊ฒ ์ฐ์ ๋๋ค. ๋ํ, ์ด ์๊ณ ๋ฆฌ์ฆ์ ์ปดํจํฐ๊ฐ ํน์ ๋ฒ์ ๋ด์ ์์๋ฅผ ๋น ๋ฅด๊ณ ํจ์จ์ ์ผ๋ก ์ฐพ๋ ๋ฐ์๋ ์ฐ์ ๋๋ค.
์ํธํ์์๋ ๋๊ท๋ชจ ์์๋ฅผ ์ฐพ๋ ๊ฒ์ด ์ค์ํฉ๋๋ค. ์ด๋ ๊ณต๊ฐ ํค ์ํธํ, ๋์งํธ ์๋ช ๋ฑ์์ ํ์์ ์ธ ์์์ ๋๋ค. ์๋ผํ ์คํ ๋ค์ค์ ์ฒด๋ ์ด๋ฌํ ํฐ ์์๋ฅผ ์ฐพ๋ ์ด๊ธฐ ๋จ๊ณ์์ ํ์ฉ๋ ์ ์์ผ๋ฉฐ, ์ปดํจํฐ ์๊ณ ๋ฆฌ์ฆ์ ํจ์จ์ฑ์ ๋์ด๋ ๋ฐ ๊ธฐ์ฌํฉ๋๋ค.
์๋ผํ ์คํ ๋ค์ค์ ์ฒด์ ํ๊ณ์ ํ๋์ ์์ฉ
๋น๋ก ์๋ผํ ์คํ ๋ค์ค์ ์ฒด๊ฐ ํจ์จ์ ์ธ ๋ฐฉ๋ฒ ์ค ํ๋์ง๋ง, ๋งค์ฐ ํฐ ์์ ๋ํด์๋ ์๊ฐ๊ณผ ๋ฉ๋ชจ๋ฆฌ ๋ฉด์์ ํ๊ณ๋ฅผ ๊ฐ์ง๊ณ ์์ต๋๋ค. ์ด๋ฅผ ๊ฐ์ ํ๊ธฐ ์ํด ํ๋์ ์ปดํจํฐ ๊ณผํ์๋ค์ ์ฌ๋ฌ ๊ฐ์ง ์ต์ ํ ๊ธฐ๋ฒ์ ๋์ ํ๊ณ ์์ต๋๋ค. ์๋ฅผ ๋ค์ด, ๋ฉ๋ชจ๋ฆฌ ์ฌ์ฉ์ ์ค์ด๊ธฐ ์ํด ๋นํธ๋งต์ ์ฌ์ฉํ๊ฑฐ๋, ๋ณ๋ ฌ ์ฒ๋ฆฌ๋ฅผ ํตํด ๊ณ์ฐ ์๋๋ฅผ ๋์ด๋ ๋ฐฉ๋ฒ ๋ฑ์ด ์์ต๋๋ค.
์ด๋ฌํ ์ต์ ํ๋ฅผ ํตํด ์๋ผํ ์คํ ๋ค์ค์ ์ฒด๋ ๋์ฉ๋ ๋ฐ์ดํฐ๋ฅผ ์ฒ๋ฆฌํ๋ ๋น ๋ฐ์ดํฐ ๋ถ์์ด๋, ๋ณต์กํ ์ํธ ์๊ณ ๋ฆฌ์ฆ์์๋ ์ฌ์ ํ ์ ์ฉํ๊ฒ ์ฌ์ฉ๋ฉ๋๋ค. ๋ฐ๋ผ์, ์ด ๊ณ ๋์ ์๊ณ ๋ฆฌ์ฆ์ด ํ๋ ๊ธฐ์ ๊ณผ ๊ฒฐํฉํ์ฌ ์๋ก์ด ๊ฐ์น๋ฅผ ์ฐฝ์ถํ๊ณ ์์ต๋๋ค.
์๋ผํ ์คํ ๋ค์ค์ ์ฒด๋ ๊ณ ๋ ๊ทธ๋ฆฌ์ค ์๋์ ๋ฐ๊ฒฌ๋ ๊ฐ๋จํ๋ฉด์๋ ํจ์จ์ ์ธ ์์ ์ฐพ๊ธฐ ์๊ณ ๋ฆฌ์ฆ์ ๋๋ค. ์ด ๋ฐฉ๋ฒ์ ์ํ๊ณผ ์ปดํจํฐ ๊ณผํ, ํนํ ์ํธํ์์ ์ค์ํ ์ญํ ์ ํ๋ฉฐ, ์ค๋๋ ์๋ ์ฌ์ ํ ๊ด๋ฒ์ํ๊ฒ ์์ฉ๋๊ณ ์์ต๋๋ค. ํ๋ ๊ธฐ์ ์ ๋ฐ์ ๊ณผ ํจ๊ป ์ต์ ํ๋์ด ๊ฐ๋ฉด์, ์ด ๊ณ ๋์ ์งํ๋ ๋์ฑ ๋ฐ์ ๋ ํํ๋ก ์ฐ๋ฆฌ ์ถ ์์ ์ค๋ฉฐ๋ค๊ณ ์์ต๋๋ค.
์๋ผํ ์คํ ๋ค์ค์ ์ฒด๋ฅผ ํ์ฉํ JS ์์ ์ฐพ๊ธฐ ๋ก์ง ๊ตฌํํ๊ธฐ
์๋ผํ ์คํ ๋ค์ค์ ์ฒด๋ ์ํ์ ์๊ณ ๋ฆฌ์ฆ ์ค ํ๋๋ก, ํน์ ๋ฒ์ ๋ด์์ ๋ชจ๋ ์์๋ฅผ ์ฐพ๋ ๋ฐ ์ฌ์ฉ๋ฉ๋๋ค. ์ด ์๊ณ ๋ฆฌ์ฆ์ ๊ณ ๋ ๊ทธ๋ฆฌ์ค ์ํ์ ์๋ผํ ์คํ ๋ค์ค๊ฐ ๋ง๋ค์์ผ๋ฉฐ, ํจ์จ์ ์ธ ์์ ์ฐพ๊ธฐ ๋ฐฉ๋ฒ์ผ๋ก ๋๋ฆฌ ์๋ ค์ ธ ์์ต๋๋ค. ์ฌ๊ธฐ์๋ ์๋ฐ์คํฌ๋ฆฝํธ๋ฅผ ์ฌ์ฉํ์ฌ ์๋ผํ ์คํ ๋ค์ค์ ์ฒด ์๊ณ ๋ฆฌ์ฆ์ ๊ตฌํํ๋ ๋ฐฉ๋ฒ์ ์๊ฐํ๊ฒ ์ต๋๋ค.
์๋ผํ ์คํ ๋ค์ค์ ์ฒด ์๊ณ ๋ฆฌ์ฆ ์ดํดํ๊ธฐ
์๋ผํ ์คํ ๋ค์ค์ ์ฒด ์๊ณ ๋ฆฌ์ฆ์ ๋ค์๊ณผ ๊ฐ์ ๋จ๊ณ๋ก ์์๋ฅผ ์ฐพ์ต๋๋ค:
- ๋ชจ๋ ์ซ์๋ฅผ ์์๋ก ๊ฐ์ ํฉ๋๋ค.
- 2๋ถํฐ ์์ํ์ฌ, ํน์ ์ซ์์ ๋ฐฐ์๋ค์ ๋ชจ๋ ์์๊ฐ ์๋ ๊ฒ์ผ๋ก ํ์ํฉ๋๋ค.
- ๋ค์ ์์๋ฅผ ์ฐพ์ ๊ทธ ๋ฐฐ์๋ค์ ์ ๊ฑฐํฉ๋๋ค.
- ์ด ๊ณผ์ ์ ๋ฐ๋ณตํ์ฌ ์์๋ง ๋จ๊น๋๋ค.
์๋ฐ์คํฌ๋ฆฝํธ๋ก ์๋ผํ ์คํ ๋ค์ค์ ์ฒด ๊ตฌํํ๊ธฐ
์๋ฐ์คํฌ๋ฆฝํธ๋ฅผ ์ฌ์ฉํ์ฌ ์ด ์๊ณ ๋ฆฌ์ฆ์ ๊ตฌํํ๋ ๊ฒ์ ๋น๊ต์ ๊ฐ๋จํฉ๋๋ค. ์๋๋ ๊ธฐ๋ณธ์ ์ธ ๊ตฌํ ๋ฐฉ๋ฒ์ ๋๋ค:
function findPrimes(n) {
let array = [], upperLimit = Math.sqrt(n), output = [];
// ๋ฐฐ์ด์ ์ด๊ธฐํํฉ๋๋ค
for (let i = 0; i < n; i++) {
array.push(true);
}
// ์๋ผํ ์คํ
๋ค์ค์ ์ฒด ์๊ณ ๋ฆฌ์ฆ ์ ์ฉ
for (let i = 2; i <= upperLimit; i++) {
if (array[i]) {
for (let j = i * i; j < n; j += i) {
array[j] = false;
}
}
}
// ์์๋ฅผ ๋ฐฐ์ด์ ์ถ๊ฐ
for (let i = 2; i < n; i++) {
if(array[i]) {
output.push(i);
}
}
return output;
}
// ์์: 30๊น์ง์ ์์ ์ฐพ๊ธฐ
console.log(findPrimes(30));
์๊ณ ๋ฆฌ์ฆ ์ต์ ํ
์ด ๊ธฐ๋ณธ ์๊ณ ๋ฆฌ์ฆ์ ์์ ์ซ์์ ๋ํด์๋ ์ ์๋ํ์ง๋ง, ๋งค์ฐ ํฐ ์ซ์ ๋ฒ์์ ๋ํด์๋ ๋นํจ์จ์ ์ผ ์ ์์ต๋๋ค. ์ฑ๋ฅ์ ํฅ์์ํค๊ธฐ ์ํด ๋ค์๊ณผ ๊ฐ์ ์ต์ ํ๋ฅผ ๊ณ ๋ คํ ์ ์์ต๋๋ค:
- ๋ฉ๋ชจ๋ฆฌ ์ฌ์ฉ๋์ ์ค์ด๊ธฐ ์ํด ๋นํธ ์ฐ์ฐ์ ์ฌ์ฉํ ์ ์์ต๋๋ค.
- ๋ฉํฐ ์ค๋ ๋ฉ์ด๋ ์น ์์ปค๋ฅผ ์ฌ์ฉํ์ฌ ๊ณ์ฐ์ ๋ณ๋ ฌ ์ฒ๋ฆฌํ ์ ์์ต๋๋ค.
- ๋ฐฐ์ด ๋์ ๋ค๋ฅธ ์๋ฃ๊ตฌ์กฐ๋ฅผ ์ฌ์ฉํ์ฌ ๋ฉ๋ชจ๋ฆฌ ์ ๊ทผ ์๊ฐ์ ์ต์ ํํ ์ ์์ต๋๋ค.
์๋ผํ ์คํ ๋ค์ค์ ์ฒด๋ ์์๋ฅผ ์ฐพ๋ ๊ฐ๋ ฅํ๊ณ ํจ์จ์ ์ธ ๋ฐฉ๋ฒ์ ๋๋ค. ์๋ฐ์คํฌ๋ฆฝํธ๋ฅผ ์ด์ฉํ ๊ตฌํ์ ๊ฐ๋จํ๋ฉฐ, ํ์์ ๋ฐ๋ผ ๋ค์ํ ์ต์ ํ๋ฅผ ์ ์ฉํ ์ ์์ต๋๋ค. ์ด ์๊ณ ๋ฆฌ์ฆ์ ํ์ฉํ์ฌ ๋ค์ํ ์ํ์ ๋ฌธ์ ํด๊ฒฐ์ ๋์ ํด๋ณด์ธ์.
ํค์๋
- ์๋ผํ ์คํ ๋ค์ค์ ์ฒด, ์๋ฐ์คํฌ๋ฆฝํธ, ์์ ์ฐพ๊ธฐ, ์๊ณ ๋ฆฌ์ฆ, ์ต์ ํ, ๋ฉ๋ชจ๋ฆฌ ์ฌ์ฉ, ๋ณ๋ ฌ ์ฒ๋ฆฌ, ์๋ฃ๊ตฌ์กฐ, ์ํ์ ๋ฌธ์ ํด๊ฒฐ, ํ๋ก๊ทธ๋๋ฐ.
ํค์๋
- ์๋ผํ ์คํ ๋ค์ค์ ์ฒด, ์์ ์ฐพ๊ธฐ, ์๊ณ ๋ฆฌ์ฆ, ์ํ, ์ปดํจํฐ ๊ณผํ, ์ํธํ, ํ๋ก๊ทธ๋๋ฐ ๊ต์ก, ์ต์ ํ ๊ธฐ๋ฒ, ๋น ๋ฐ์ดํฐ, ๊ณ ๋ ๊ทธ๋ฆฌ์ค
๋๊ธ