소수를 찾아내는 알고리즘

맨날 툭하면 계속 나오는 소수문제
이해가 안됐는데 암호화를 소수를 사용해서 이렇게 문제가 자주 나온다는 이야기를 들었다...

그 중 에라토스테네스의 체라는 것이 있는데

쉽게 생각해서 다양한 방법으로 소인수 분해를 한 다음에 안되는 것들만 뱉어내는 것이다.

그것을 코드로 구현한 분이 많았는데, 일단 그것을 바탕으로 이것저것 맛보려고 한다

코드 참고한 블로그 > JS 프로그래머스 소수 만들기 <

들어온 값이 소수인지, 아닌지

const isPrime = (n) => {
  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (n % i === 0) {
      return false;
    }
  }
  return true;
}

요것은 인자에 숫자를 넣을 경우 반환을 true or false로 반환을 해주는 함수다.

근데 보통 이런것만 원하는게 아니라 여러가지 버전(?)을 원하는데

소수인 수, 소수가 아닌 수 출력

let real = []
let untrue = []
const isPrime = (n) => {
  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (n % i === 0) {
      return untrue.push(n)
    }
  }
  return real.push(n);
}
arr.forEach(ele,=> isPrime(ele))

소수의 갯수를 출력 (인자가 배열)

let count = 0
const isPrime = (n) => {
  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (n % i === 0) {
      return false;
    }
  }
  return true;
}
arr.forEach(ele=> isPrime(ele) === true ? count+=1 : false)

이정도면 될 것 같다. . . . 이거면 어지간해선 다 풀 수 있지 않으까,,,, , .?

소수의 갯수를 출력 (인자가 숫자)

function solution(n) {
  let arr = [];
  for (let i = 2; i <= n; i++) {
    arr.push(i);
  }
  let count = 0;
  const isPrime = (n) => {
    for (let i = 2; i <= Math.sqrt(n); i++) {
      if (n % i === 0) {
        return false;
      }
    }
    return true;
  };
  arr.forEach((ele) => (isPrime(ele) === true ? (count += 1) : false));
  return count;
}

정말 위에꺼 복사해다가 들어오는 값을 배열로 바꿔서 풀었다.
이거...어케...통과했지?
이러면 과정이 정말 복잡해져서 덜 복잡하게 풀어보려고 했다.

만약에 인자가 숫자로 들어온다면

1. 인자에서 계속 1씩 뺀다
2. 그 값으로 소수인지 아닌지 판단한다
3. 소수라면 count+1 아니면 그냥 진행한다
   이런식으로 하면 될 것 같은데 마음처럼 굴러가질 않는다
   음..음음