[에라토스테네스의 체] 소수 찾기

Problem. 소수 찾기

---

Link.

https://school.programmers.co.kr/learn/courses/30/lessons/12921

프로그래머스

---

Problem.

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만드시오.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다

(1은 소수가 아닙니다)

 

제한사항

1. n은 2이상 1,000,000이하의 자연수입니다.

 

입출력 예시

// case#1
n = 10;
return = 4;

// case#2
n = 5
return = 3

---

My Answer. 

// 에라토스테네스의 체
function get_primes(num) {
	// 0과 1은 소수이므로 false 처리
    const prime = [false, false, ...Array(num - 1).fill(true)];
    
    for (let i = 2; i * i <= num; i++) {
        if (prime[i]) {
        	// i의 배수를 false 처리 (소수에서 제외)
            for (let j = i * 2; j <= num; j = j + i) {
                prime[j] = false
            }
        }
    }
    // true 값만 반환
    return prime.filter(Boolean);
}

function solution(n) {
    return get_primes(n).length;
}

---

References.

• 코딩테스트 광탈 방지 A to Z : JavaScript (이선협)

---

For Developer. 

• 잘못되거나 부족한 부분이 있다면 언제든지 댓글 부탁드립니다 :)