๐ฉ๐ปโ๐ป๋ฌธ์ ๋งํฌ
๋ฌธ์ ์ค๋ช
1๋ถํฐ ์
๋ ฅ๋ฐ์ ์ซ์ n ์ฌ์ด์ ์๋ ์์์ ๊ฐ์๋ฅผ ๋ฐํํ๋ ํจ์, solution์ ๋ง๋ค์ด ๋ณด์ธ์.
์์๋ 1๊ณผ ์๊ธฐ ์์ ์ผ๋ก๋ง ๋๋์ด์ง๋ ์๋ฅผ ์๋ฏธํฉ๋๋ค.
(1์ ์์๊ฐ ์๋๋๋ค.)
์ ํ ์กฐ๊ฑด
n์ 2์ด์ 1000000์ดํ์ ์์ฐ์์
๋๋ค.
์
์ถ๋ ฅ ์
n result
10 4
5 3
์
์ถ๋ ฅ ์ ์ค๋ช
์
์ถ๋ ฅ ์ #1
1๋ถํฐ 10 ์ฌ์ด์ ์์๋ [2,3,5,7] 4๊ฐ๊ฐ ์กด์ฌํ๋ฏ๋ก 4๋ฅผ ๋ฐํ
์
์ถ๋ ฅ ์ #2
1๋ถํฐ 5 ์ฌ์ด์ ์์๋ [2,3,5] 3๊ฐ๊ฐ ์กด์ฌํ๋ฏ๋ก 3๋ฅผ ๋ฐํ
โ๏ธIdea Sketch
2021-06-17 isPrime()
- isPrime(num) ํจ์ ์์ฑ --> output: true/false
- 1๋ถํฐ n๊น์ง isPrime()ํจ์๋ฅผ ์ฌ์ฉํด ์์์ฌ๋ถ๋ฅผ ํ๋ณ
- ์์์ธ์ง ์๋์ง ํ๋ณํ๋ ๋ฐฉ๋ฒ์? 1๊ณผ ์๊ธฐ์์ ์ ์ ์ธํ๊ณ ๋๋์ด๋จ์ด์ง๋ ์๊ฐ ์๋๊ฐ?
- ๋ฐ๋ณต๋ฌธ for(let i=2; i
์ฒ์๋ถํฐ ๋๊น์ง ํ์ธํ ํ์๊ฐ ์์๊น? - ์ง์๋ฉด i=2์์ ๋ฐ๋ก ๊ฑธ๋ฌ์ง๊ณ ์ข ๋ฃ. return False
- ๋ฐ๋ณต๋ฌธ for(let i=2; i<=num/2; i++) --> num์ด 25์ธ ๊ฒฝ์ฐ, 2๋ถํฐ 12๊น์ง ํ์ธ
- ๋ฐ๋ณต๋ฌธ for(let i=2; i<=Math.sqrt(num); i++) --> num์ด 25์ธ ๊ฒฝ์ฐ, 2๋ถํฐ 5๊น์ง ํ์ธ
- ํ์๋ฉด ์ ๊ณฑ์๊น์ง ํ์ธ
- ๋ฐ๋ณต๋ฌธ for(let i=2; i
2021-06-17 ์๋ผํ ์คํ ๋ค์ค์ ์ฒด
- length๋ n, value๋ 0/1์ธ ๋ฐฐ์ด ๋ง๋ค๊ธฐ
let arr = Array.from({length:n+1}, () => 0)
- ์ฒด์ ๊ฑธ๋ฌ์ง ๊ฒฝ์ฐ, 1๋ก ๋ฐ๊พธ๊ธฐ
- ๋ฐฐ์ด๊ฐ์ด 0์ธ ๊ฒฝ์ฐ, ์์
- i์ ๋ฐฐ์์ธ ๊ฒฝ์ฐ, ๋ฐฐ์ด๊ฐ์ 1๋ก ์ ์ฅ
if (arr[i] === 0) {
cnt++;
for (let j=1; i*j<=n; j++) arr[i*j] = 1
}
- isPrime()์ ํ์์์!!
โ๏ธ์์ค์ฝ๋
2021-06-17 isPrime() ์ฌ์ฉ --> ์ ํ์ฑ ํต๊ณผ, ํจ์จ์ฑ ํ๋ฝ
function isPrime(num) {
for (let i=2; i<=Math.sqrt(num); i++) {
if (num%i===0) return false;
}
return true;
}
function solution(n) {
let cnt = 0;
for (let i=2; i<=n; i++) {
if (isPrime(i)) cnt++;
}
return cnt
}
2021-06-17 isPrime()์ ์๋ผํ ์คํ ๋ค์ค์ ์ฒด ํผ์ฉ --> ์ ํ์ฑ ํต๊ณผ, ํจ์จ์ฑ ํ๋ฝ
function isPrime(num) {
for (let i=2; i<=Math.sqrt(num); i++) {
if (num%i===0) return false;
}
return true;
}
function solution(n) {
let cnt = 0;
let arr = Array.from({length:n+1}, () => 0)
for (let i=2; i<=n; i++) {
if (arr[i] === 0) {
if (isPrime(i)) {
cnt++;
for (let j=1; i*j<=n; j++) arr[i*j] = 1
}
}
}
return cnt
}
2021-06-17 ์๋ผํ ์คํ ๋ค์ค์ ์ฒด --> ์ ํ์ฑ ํต๊ณผ, ํจ์จ์ฑ ํต๊ณผ
function solution(n) {
let cnt = 0;
let arr = Array.from({length:n+1}, () => 0)
for (let i=2; i<=n; i++) {
if (arr[i] === 0) {
cnt++;
for (let j=1; i*j<=n; j++) arr[i*j] = 1
}
}
return cnt
}
โ๏ธ๋ช ๋ต
Set ์ฌ์ฉํ๊ธฐ + Math.sqrt(n)
function solution(n) {
const s = new Set();
for(let i=1; i<=n; i+=2){
s.add(i);
}
s.delete(1);
s.add(2); // Set์ ํ์๋ง ์ ์ฅ -> 1 ์ญ์ -> 2 ์ถ๊ฐ
for(let j=3; j<=Math.sqrt(n); j++){
if(s.has(j)){
for(let k=j*2; k<=n; k+=j){ // j์ ๋ฐฐ์(k) ์ญ์
s.delete(k);
}
}
}
return s.size;
}
- Set์ ์ค๋ณต์๋ ๋ฐฐ์ด
let mySet = new Set();
let mySet = new Set([1, 2, 3, 4, 5]);
mySet.add( 6 );
- Set์ array๋ก ๋ง๋๋ ๋ฐฉ๋ฒ
let arr = Array.from(mySet)
let arr = Array.from(mySet).sort((a, b) => b-a);
- Set ์ฐ์ฐ
s.delete(1);
s.add(2);
s.has(2);
s.size;