[프로그래머스 12921] 소수 찾기 (Javascript)

👩🏻‍💻문제링크

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

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

제한 조건
n은 2이상 1000000이하의 자연수입니다.
입출력 예
n result
10 4
5 3
입출력 예 설명
입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

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

✍️Idea Sketch

2021-06-17 isPrime()

1. isPrime(num) 함수 생성 --> output: true/false
2. 1부터 n까지 isPrime()함수를 사용해 소수여부를 판별
3. 소수인지 아닌지 판별하는 방법은? 1과 자기자신을 제외하고 나누어떨어지는 수가 있는가?
   • 반복문 for(let i=2; i 처음부터 끝까지 확인할 필요가 있을까?
   • 짝수면 i=2에서 바로 걸러지고 종료. return False
   • 반복문 for(let i=2; i<=num/2; i++) --> num이 25인 경우, 2부터 12까지 확인
   • 반복문 for(let i=2; i<=Math.sqrt(num); i++) --> num이 25인 경우, 2부터 5까지 확인
   • 홀수면 제곱수까지 확인

2021-06-17 에라토스테네스의 체

1. length는 n, value는 0/1인 배열 만들기

  let arr = Array.from({length:n+1}, () => 0)

2. 체에 걸러진 경우, 1로 바꾸기
   • 배열값이 0인 경우, 소수
   • i의 배수인 경우, 배열값을 1로 저장

  if (arr[i] === 0) {
    cnt++;
    for (let j=1; i*j<=n; j++) arr[i*j] = 1
  }

3. isPrime()은 필요없음!!

✍️소스코드

2021-06-17 isPrime() 사용 --> 정확성 통과, 효율성 탈락

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

function solution(n) {
  let cnt = 0;
  for (let i=2; i<=n; i++) {
    if (isPrime(i)) cnt++;
  }
  return cnt
}

2021-06-17 isPrime()와 에라토스테네스의 체 혼용 --> 정확성 통과, 효율성 탈락

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

function solution(n) {
  let cnt = 0;
  let arr = Array.from({length:n+1}, () => 0)
  for (let i=2; i<=n; i++) {
    if (arr[i] === 0) {
      if (isPrime(i)) {
        cnt++;
        for (let j=1; i*j<=n; j++) arr[i*j] = 1
      }
    }
  }
  return cnt
}

2021-06-17 에라토스테네스의 체 --> 정확성 통과, 효율성 통과

function solution(n) {
  let cnt = 0;
  let arr = Array.from({length:n+1}, () => 0)
  for (let i=2; i<=n; i++) {
    if (arr[i] === 0) {
        cnt++;
        for (let j=1; i*j<=n; j++) arr[i*j] = 1
    }
  }
  return cnt
}

✍️명답

Set 사용하기 + Math.sqrt(n)

function solution(n) {
    const s = new Set();
    for(let i=1; i<=n; i+=2){
        s.add(i);
    }
    s.delete(1);
    s.add(2); // Set에 홀수만 저장 -> 1 삭제 -> 2 추가
    for(let j=3; j<=Math.sqrt(n); j++){ 
        if(s.has(j)){
             for(let k=j*2; k<=n; k+=j){ // j의 배수(k) 삭제
                s.delete(k);
             }
        }
    }
    return s.size;
}

1. Set은 중복없는 배열

let mySet = new Set();
let mySet = new Set([1, 2, 3, 4, 5]);
mySet.add( 6 );

2. Set을 array로 만드는 방법

let arr = Array.from(mySet)
let arr = Array.from(mySet).sort((a, b) => b-a);

3. Set 연산

s.delete(1);
s.add(2);
s.has(2);
s.size;