TIL-23.04.10

 

프로그래머스 소수 찾기 

 

문제점

알고리즘 문제의 제한 조건인 숫자n의 범위가 1,000,000 이라는 것때문에 테스트 결과 중 시간초과가 나옴

const solution = (n) => {
  let answer = 0;
  for (let i = 1; i <= n; i++) {
    decimal(i) ? answer++ : null;
  }
  return answer;
};
const decimal = (num) => {
  if (num < 2) return false;

  for (let i = 2; i <= num; i++) {
    if (num % i === 0) {
      return false;
    }
  }
  return true;
};

시간초과 결과가 나온 첫번째 코드

소수를 판별하는 decimal 함수에서 2부터 매개변수까지 모든 숫자를 반복했다. 이로인해 시간초과가 나온것

 

 

 

시도해본것 && 해결

테스트결과가 실패가 아닌 시간초과가 나온것이기때문에 전체적인 코드상으론 문제가 없다고 생각했다

그러면.. 반복문이 테스트를 통과하지 못하게 만들었을건데.. 라는 생각으로 반복문 조건을 다시 생각해보았다.

구글링해본 결과 해당 숫자의 소수 판별은 해당 숫자의 제곱근 까지만 판별하면 된다는 수학적(?)지식을 얻게되었다!

예를 들어 자연수 16의 소수판별은 16의 제곱근 4까지만 검사를 하면 해당 숫자의 소수판별 여부를 알수있다는것이다

이 수학적지식을 바탕으로 다시 작성해본 코드!

const solution = (n) => {
  let answer = 0;
  for (let i = 1; i <= n; i++) {
    decimal(i) ? answer++ : null;
  }
  return answer;
};
const decimal = (num) => {
  if (num < 2) return false;

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

처음 작성했던 코드와 달라진건 decimal 함수 내부 ' Math.floor(Math.sqrt(num)) ' 이것 뿐이다

어차피 1은 소수가 아니므로 2부터 반복을 시작했고, 해당 숫자의 제곱근까지만 반복을 해 소수여부를 판별했다. 그러니 당연하게 반복횟수는 확 줄어들게 될것이고, 해당 코드가 돌아가는 시간 또한 짧아질것이다.

예를 들어 숫자 10,000까지의 자연수 중 소수를 판결하려면 2부터 10,000까지 9999번의 반복을 해야하지만,

10,000의 제곱근 100까지 반복을 하게된다면 단지 99번의 반복만 하면된다 9999 / 99 반복횟수 차이가 너무 나네..

 

 

알게된점

수학적 지식이긴 하지만 앞으로 해당 숫자의 소수여부를 판별할때 해당숫자의 제곱근까지만 계산하면 된다는 중요한 사실을 알게되었다!