알고리즘 문제풀이 10

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

정수론에 대한 참고 블로그
소수에 대한 알고리즘 문제는 크게 두 가지이다
1. 소수인지 아닌지?
2. 주어진 숫자 범위내에서 소수 골라내기

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

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

• 참고 1 : https://stackoverflow.com/questions/40200089/number-prime-test-in-javascript
• 참고 2 : https://www.thepolyglotdeveloper.com/2015/04/determine-if-a-number-is-prime-using-javascript/

var primeTester = function (n) {
  if (typeof n !== 'number' || n <= 1 || !Number.isInteger(n)) {
    // n 이 숫자가 아니거나 n이 1보다 작거나 or n이 정수가 아닌 경우
    //n%1!==0 처럼 소수인지 정수인지를 점검하는 건 메소드를 써준다
    return false;
  } else if (n === 2) {
    return true; //즉 n이 1이거나 2일 때 소수이다
    //1은 소수가 아니라서  n<=2가 아니라 n===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;
//};

에라토스테네의 체에 대한 이해가 핵심

개념에 대한 이해는 완료되었고, 코드 구현이 중요했다.
해당 알고리즘 코드는 같이 공부하는 동기분의 코드가 리뷰 후에도 가장
효율적이라는 결론이 나와서, 참고하기로 하여 가지고 온 것이다.

구체적인 설명은 상단의 링크를 참고하면 된다!
(현정님의 블로그는 항상 최고다)

//소수문제풀 때 항상 조심해야하는 두 수: 1은 소수가 아니다. 2는 소수이다.
//다 소수(true)라고 치고, 소수가 아닌 것(false)을 제외시켜 나간다.

var primeSieve = function (start, end) {
  let Era = []; //start부터 end까지의 수가 차례대로 들어가있는 배열
  for (let i = start; i <= end; i++) {
    Era.push(i);
  } //끝까지 Era 배열에 남아있는수가 소수들이다.
  if (start === 1) {
    Era.splice(0, 1);
  } //1은 소수가 아니고 모두가 다 1의 배수이므로 처음부터 제외하고 시작한다.
  //에라토스테네스의 체 시작

  let inx = 0;
  let len = Era.length;
  for (let i = 0; i < len; i++) {
    let curr = Era[inx];
    if (curr === undefined) {
      return Era;
    }
    //console.log(Era, curr)
    if (primeTester(curr)) {
      //소수이면 그것만 놔두고
      for (let mul = 2 * curr; mul <= end; mul += curr) {
        //그것의 배수는 다 제거
        if (Era.includes(mul)) {
          Era.splice(Era.indexOf(mul), 1);
        }
      }
      inx++;
    } else {
      //소수 아니면 제거
      Era.splice(Era.indexOf(curr), 1);
    }
  }
  //남은게 소수들로 구성된 배열
  return Era;
};