programmers 코딩테스트 : 소수 찾기

🔔 소수 찾기

📢 문제 설명
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

⛔ 제한 조건
n은 2이상 1000000이하의 자연수입니다.

---

🔠 첫번째 시도한 코드

~~9번까지 통과한 코드 ~~

function solution(n) {
  let answer = 0;
  let arr = [];
  let newArr = [];
  //1. n만큼의 배열 만들기
  for (let i = 1; i <= n; i++) {
    arr.push(i);
  }
  // 2. 해당 배열을 가지고 map으로 el을 뺴줌
  arr.map((el) => {
    for (let j = 2; j <= n; j++) {
      if(el % j === 0) {
        if(el === j) newArr.push(j);
        break;
      }
    }
  });
  answer = newArr.length;
  return answer;
}

📌 코드 설명

1. n의 길이를 가진 1부터 n까지의 array를 만든다.
2. 해당 배열을 가지고 map((el) => )
3. i는 2부터 시작하고 점차 증가하는 for()문 시작
4. 첫번째 if : el 나누기 j의 나머지가 없는 경우
5. 두번째 if : el이 j와 같은 경우 newArr에 j를 push
6. answer는 newArr의 길이
7. return answer;

map안에 for문이 있어 n의 숫자가 크면 클수록 시간 초과가 뜨는 경우가 있는 것 같다. 효율성도 시간 초과가 뜨는 것으로 보아.. 다른 식으로 진행하기로 합니다.

---

🔠 두번째 통과한 코드 (에라토스테네스의 체)

function solution(m){
  let arr = Array(m+1).fill(true).fill(false, 0 , 2)       
  for (let i = 2; i*i<=m; i++){
    for(let j = i*i; j<=m; j+=i){ // 배수 찾기
      arr[j] = false;
    }
  }
  return arr.filter(el => el).length
}

📌 코드 설명

1. 배열 생성
   1-1. m +1의 길이를 가진 배열
   1-2. 해당 배열은 true로 채웠다가,
   1-3. 0,1은 false로 바꾼다.
2. 첫번째 for()문
   2-1. 조건
   1. i는 2부터 시작 (소수는 2부터 시작함)
   2. i = 제곱근이라고 생각 했을 때 i*i는 m 이상이 될 수 없음
   3. i++

• 해당 i 는 j의 순서가 됨... *

3. 두번째 for()문
   3-1. 조건
   1. j는 i*i
   2. j는 m 작거나 같음
   3. j는 i+1
4. arr.filter(el => el).length // true만 추출 후 개수 return