소수 찾기

Posted on Edited on In Word count in article: 174 Reading time ≈ 1 mins.

문제

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

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

제한조건

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

입출력 예

n result
10 4
5 3

풀이방향

  • 입력된 숫자의 소수를 구하고
  • 소수의 개수를 리턴한다

문제풀이

primeNumber.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function primeNumber(num) {
  //소수의 개수 구하기
  let count = 0;
  let n = num;
  while (n > 1) {
    let temp = Math.floor(Math.sqrt(n));
    let isPrime = true;
    for (let i = 2; i <= temp; i++) {
      if (n % i === 0) {
        isPrime = false;
        break;
      }
    }
    if (isPrime) {
      count++;
    }
    n--;
  }
  return count;
}

export { primeNumber };
primeNumber.test.js
1
2
3
4
5
6
7
8
9
10
import { primeNumber } from "../src/primeNumber";

describe("primeNumber", () => {
  it("should return 4 for 10", () => {
    expect(primeNumber(10)).toBe(4);
  });
  it("should return 3 for 5", () => {
    expect(primeNumber(5)).toBe(3);
  });
});

문제출처

  • 프로그래머스

다른 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function solution(n) {
    const s = new Set();
    for(let i=1; i<=n; i+=2){
        s.add(i);
    }
    s.delete(1);
    s.add(2);
    for(let j=3; j<Math.sqrt(n); j++){
        if(s.has(j)){
             for(let k=j*2; k<=n; k+=j){    
                s.delete(k);
             }
        }
    }
    return s.size;
}