[JavaScript] 백준 기본수학2 #1978번 소수 찾기

https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

---

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력

첫 줄에 수의 개수 N이 주어진다. N은 100 이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

주어진 수들 중 소수의 개수를 출력한다.

예제 입력1

4
1 3 5 7

예제 출력 1

3

해결 방법

소수를 찾는 방법은 여러 가지가 있다.

먼저 범위 내의 모든 수로 나눠보고 나머지가 0이 아닌 경우 소수이다. 하지만 숫자를 하나하나 확인해야 해서 속도가 느리다.

그래서 속도를 올리기 위해 활용할 수 있는 방법이  √N 까지 구하는 방법이다.

 

예를 들어 n=12이라고 해보자.

12의 약수는 1, 2, 3, 4, 6 , 12이고 (1, 12), (2, 6), (3, 4)로 묶이기 때문에 3까지만 나눴을 때 나머지 값을 확인하면 이후의 값은 확인할 필요가 없다.

따라서 12의 루트 값이 3. 4... 이기 때문에 루트 값까지만 나머지를 확인하면 된다.

 

하지만 코드 상으로 루트를 나타내는 것보다 제곱 값을 나타내는 것이 편하기 때문에 범위를 i의 제곱 값으로 해준 것이다. 

전체 코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const arr = input[1].split(' ').map(Number);

let arr1 = [];


function prime(num){
    if( num <= 1) return;

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

    arr1.push(num);
}

arr.map((e) => {prime(e)});

console.log(arr1.length);

참고 사이트

소수(Prime Number) 구하기 효율적 알고리즘 :: 코드자몽 (tistory.com)

소수(Prime Number) 구하기 효율적 알고리즘 :: 코드자몽