프로그래머스 1단계 - 소수찾기

< 문제 >

풀이 2개 (에라토스테네스의 체 풀이만 통과✅)

에라토스테네의 체 정리 (동빈나 유튜브)

에라토스테네스의 체 ✅
먼저 받아온숫자길이만큼 fill을 이용해 true로 채워진 배열을 만들어준다.
그리고 answer[0]은 배열은 index-1 이므로 1인데 소수에서 1은 항상 소수가 아니기때문에
먼저 index 0번째는 항상 false가 되도록 flase를 넣어준다.


그 이후 반복문을 돌면서 i를 제곱근을 이용해 반복횟수를 줄여주는 방식으로 진행하고,
answer의 index자리에 이중for문으로 도는 (i의 제곱부터 시작해, n까지 반복, i를 더해줌) j -1번째 index에 flase를 넣어준다. 이렇게되면 소수가아닌 모든 숫자는 flase가 되고, 소수는 true가 되어서 true인 배열의 길이만 꺼내는 방식으로 풀이.


<에라토스테네스의 체는>
가장 먼저 소수를 판별할 범위만큼 배열을 할당하고 그 인덱스에 해당하는 값을 넣어준다. 약수는 대칭되므로 제곱근으로 계산가능

function isPrime(array, n) {
  for (let i = 2; i <= Math.sqrt(n); i++) {
    for (let j = i + i; j <= n; j += i) {
      if (j % i === 0) {
        array[j - 1] = false;
      }
    }
  }
}

function solution(n) {
  let array = Array(n).fill(true);
  array[0] = false;

  isPrime(array, n);
  return array.filter(item => item).length;
}

console.log(solution(10));
console.log(solution(5));

제곱근을 일반적인 소수 구하기 테스트 통과❌

function isPrime(num) {
  if (num === 1) return false;

  for (let i = 2; i <= parseInt(Math.sqrt(num)); i++) {
    if (num % i === 0) {
      return false;
    }
  }
  return true;
}

function solution(n) {
  let answer = 0;
  for (let i = 2; i <= n; i++) {
    if (isPrime(i)) answer = answer + 1;
  }
  return answer;
}

console.log(solution(10));
console.log(solution(5));