알고리즘 문제풀이 10

hyunju-song·2일 전
0

ALGORITHM

목록 보기
11/11
post-thumbnail

주어진 수가 소수인지를 점검하는 알고리즘문제이다.
소수이면 true, 소수가 아니면 false를 반환한다.
해당 알고리즘에서 핵심은 소수를 찾는 것도 있지만,
Math.sqrt() 를 활용하는 것이다.

왜 주어진 수의 제곱근보다 작은 수 중에서 주어진 수의 약수가 없으면 왜 소수일까???

이것은 주어진 수의 약수리스트가 제곱근들보다 모두 클수가 없기 때문이다.
무슨 말일까? 모든 수는 n = a b 즉, 두수의 곱으로 표현될 수 있다.
숫자 64를 예를 들어보자.
64의 제곱근은 8이므로 8
8로 표현될 수 있다.
그런데 8보다 큰 수로만 64를 표현할 수없다.
9 9 라던가, 10 9 라던가 다 64보다 크다.
즉, 주어진 수 = 제곱근보다 작은 수 * 제곱근보다 큰수 로 구성되어있으므로, 제곱근보다 작은 수들을 약수로 가지는지 안가지는 지만 확인하면 되는 것!

var primeTester = function (n) {
  if (typeof n !== 'number' || n <= 1 || n % 1 !== 0) {
    // n 이 숫자가 아니거나 n이 1보다 작거나 or n이 정수가 아닌 경우
    return false;
  } else if (n <= 2) {
    return true; //즉 n이 1이거나 2일 때 소수이다
  } else if (n > 2 && n % 2 === 0) {
    return false; //n이 2보다 크고 짝수이면 무조건 소수가 아니다
  } else {
    //? 숫자의 제곱근까지 루프를 실행하면 알고리즘의 복잡성을 O (n)에서 O (sqrt (n))로 줄일 수도 있다.
    //제곱근 활용하지 않고 그냥 숫자를 반복문을 돌다보니 테스트를 통과하지 못하고 시간복잡도가 너무 오래 걸림.

    let num = parseInt(Math.sqrt(n)); // n의 제곱근에서 소수자리 버려주고 정수화

    for (let i = 3; i <= num; i = i + 2) {
      //소수인지 알아보려 해당 조건까지 내려온 수는 1보다 큰 홀수일 것이므로, 약수인지 비교하는 수들에서 짝수는 건너뛰어도 된다.
      if (n % i === 0) {
        //약수가 하나라도 있으면 바로 false 반환
        return false;
      }
    }
    return true;
  }
};

/* Extra credit: Write a function that generates a list of all prime numbers
 * in a user-specified range (inclusive). If you're not quite sure where to start,
 * check out the Sieve of Eratosthenes on Wikipedia. (And if you're feeling
 * saucy, check out the Sieve of Atkin.)
 */

var primeSieve = function (start, end) {
  let arr = [];
  for (let i = start; i <= end; i++) {
    if (primeTester(i) === true) {
      arr.push(i);
    }
  }
  return arr;
};
profile
코드 한 줄로, 세상의 가치를 만들자🌟

0개의 댓글