[프로그래머스] 소수 찾기 in JavaScript

hyocho·2022년 8월 16일
0

코딩테스트

목록 보기
39/45

✅문제

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

  • 제한 조건
    n은 2이상 1000000이하의 자연수입니다.

  • 입출력 예 #1
    1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

  • 입출력 예 #2
    1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

✍문제풀이

1. 처음에 썼던 코드

function solution(n){
  let answer=0;
  for(let i=2; i<=n; i++){
    let yaksoo = 0;
    for(let j=1; j<=i; j++){
      if(i%j==0) yaksoo+=1;
    }
    if(yaksoo<=2) answer+=1;
  }
  return answer;
}

1은 소수가 아니므로, 2부터 n까지 반복문을 돌며
약수가 있을 때 마다 yaksoo에 +1을 해 주었고, 그 yaksoo가 2보다 같거나 작다는 것은 소수라는 뜻이므로 answer에 하나씩 더해주는 알고리즘을 썼다.
그치만 결과는.. 위와 같이 정확성/효율성에서 시간 초과로 실패했다 ㅠㅠ


수정 코드

// 소수인지 판별하는 함수
function isPrime(x) {
  for (let i = 2; i <= Math.sqrt(x); i++) {
    if (x % i === 0) return false;
  }
  return true;
}

function solution(n) {
  // 소수의 개수를 저장할 변수
  let answer = 0;
  // 1은 소수가 아니므로 2부터 n까지 모든 수에 대해
  for (let i = 2; i <= n; i++) {
    // 소수이면 소수의 개수에 1 추가
    if (isPrime(i)) answer++;
  }
  return answer;
}

인터넷에서 다른 분들의 코드를 보고 착안하여 수정된 코드
소수인지 판별하는 함수를 따로 만들었다.
참조한 사이트 3,4번에서 소수 찾기에 대한 것을 아주 상세히 설명해주셔서 도움이 많이 됐다.


에라토스테네스의 체 : 범위에서 합성수를 지우는 방식으로 소수를 찾는 방법.

  • 1은 제거
  • 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.
  • 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.
  • 지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다.
    (반복)

문제 출처 :
참조한 사이트 :
1. https://kangworld.tistory.com/20
2. https://it-jin-developer.tistory.com/47
3.https://velog.io/@loocia1910/javascript%EC%97%90%EC%84%9C-%EC%86%8C%EC%88%98Prime-number-%EA%B5%AC%ED%95%98%EA%B8%B0
4. https://medium.com/@hyunhodl/%EC%86%8C%EC%88%98-%ED%8C%90%EB%B3%84-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-with-%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-eef9007b290f

profile
기록하는 습관을 기르고 있습니다.

0개의 댓글