[Lv.1]소수 찾기(✩✩✩✩)

https://programmers.co.kr/learn/courses/30/lessons/12921
체감 난이도 : ✩✩✩✩ (제곱근으로 소수 구하는 원리 공부)

🔶 내가 한 방법

// 1. 소수인지 판별하는 함수
function isPrime(num) {
  if (num === 1) {
    return false;
  }

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

  return true;
}

// 2.숫자를 순회하면서 소수의 갯수를 구한다.
function solution(num) {
  let cnt = 0;
  for (let i = num; i >= 1; i -= 1) {
    if (isPrime(i)) {
      cnt += 1;
    }
  }
  return cnt;
}

console.log(solution(10)); // 4
console.log(solution(5)); // 3

🔶다른 사람 방법

🔶 피드백

* 소수란?

: 1과 자기 자신으로만 나눌 수 있는 숫자 (1은 소수에 미포함)
: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 6

* 소수 구하는 방법

: 해당 숫자를 '제곱근~2'로 나눈 것 중, 하나라도 나머지가 0이 나오는게 있으면 소수가 아님.

: 제곱근을 구해 '제곱근~2'까지의 해당 숫자로 나눠보는 이유?
→ 제곱근이 그 숫자의 약수 중 젤 큰 숫자이므로 제곱근을 기준으로 하나씩 -1해가며 나눠보는 것임

: ex)
12의 약수는 : 1 , 12 / 2 , 6 / 3 , 4
12의 제곱근은 : 3.454
약수 3, 2 중 하나라도 12를 나눴을때 나머지가 0이 되는게 있으면, 소수가 아닌것임

function isPrime(num) {
 // 1. 1은 소수가 아니다
    if (num === 1) {
    return false;
  }
  
 // 2. 제곱근이 1인 숫자는 무조건 소수다.
 // 3. 해당 숫자를 "2~제곱근"으로 나눈 것 중 하나라도 나머지가 0이 나오면 소수가 아님.
  for (let i = 2; i <= Math.sqrt(num); i += 1) {
    if (num % i === 0) {
      return false;
    }
  }
  
 // 4. 나머지가 0이 나오는게 없으면, 소수다.
  return true;
}

num / 제곱근( Math.sqrt(num) )
 1  /  1
 2  /  1.4142135623730951
 3  /  1.7320508075688772
 4  /  2
 5  /  2.23606797749979
 6  /  2.449489742783178
 7  /  2.6457513110645907
 8  /  2.8284271247461903
 9  /  3
 10  /  3.1622776601683795
 11  /  3.3166247903554
 12  /  3.4641016151377544
 13  /  3.605551275463989
 14  /  3.7416573867739413
 15  /  3.872983346207417
 16  /  4