알고리즘 문제 | 프로그래머스 - 소수 찾기

소수 찾기를 해보자..

 

우선, 소수란 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수!

예를 들어, 5는 1×5 또는 5×1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다.
그러나 6은 자신보다 작은 두 숫자(2×3)의 곱이므로 소수가 아님!

 

따라서

function solution(n) {
  let answer = 0;
  let count;

  for(let i=2; i<=n; i++) {
    count = 0;
    for(let j=2; j<=i; j++) {
      if(i % j == 0) {
        count++;
      }
    }
    if(count == 1) {
      answer++;
    }
  }

  return answer;
}

내가 판별하고 싶은 수 n까지 반복을 돌리자

그리고 이중 반복문을 통해서 내가 판별하고 싶은 수와 내가 판별하고 싶은 수 까지를 나눴을 때 나머지가 0이라면 카운트를 증가시켜주고!

만약 카운트가 1이라면 소수이니 카운트를 하나 증가시켜주면 끝!

 

이렇게하면 테스트도 패스하지 못할 뿐더러

숫자가 증가 됐을 때 i*j가 되니 연산이 많아져 속도가 기하급수적으로 늦춰진다 ..

 

그래서 다른 방법을 생각해야 한다..

뭐가 있을까 ..

 

---

 

 

function solution(n) {
  var demical = new Array(n).fill(true);
  demical[0] = false;

  for (var i = 2; Math.pow(i, 2) <= n; i++) {
    if (demical[i - 1] === true) {
      for (var j = Math.pow(i, 2); j <= n; j += i) {
        demical[j - 1] = false;
      }
    }
  }
  return demical.filter(function (e) {
    return e;
  }).length;
}

console.log(solution(1000));

이거 나중에 해봐라 ...

 

출처: velog.io/@dosanahnchangho/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%86%8C%EC%88%98-%EA%B5%AC%ED%95%98%EA%B8%B0-JavaScript

[프로그래머스] 소수 구하기 (JavaScript)