백준 1978 소수 찾기 [JavaScript]

문제

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

입력

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

출력

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

예제 입력 1

4
1 3 5 7

예제 출력 1

3

풀이

//2부터 X-1까지 모두 나눠서 X가 소수인지 판별하는 문제 1
const fs = require('fs')
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const N = input[0];     //주어진 수 N개
const num = input[1].trim().split(' ');       //소수인지 확인할 수
let prime = 0;      //소수의 개수

for(let i=0; i<N; i++){	//2부터 숫자를 올려가며 나누어서 소수를 판별한다.
    let count = 2;

    while(true){                 
        if(parseInt(num[i]) === 1){   //1이면 소수가 아니다.    
            break;
        }
        if(count === parseInt(num[i])){	//count가 소수를 판별하는 수와 같아졌다면 1과 자기 자신으로만 나누어지므로 이 수는 소수이다.
            prime++;
            break;
        }
        if(parseInt(num[i])%count === 0){	//1과 자기자신이 아닌 수 count로 나누어떨어졌다면 이 수는 소수가 아니다.
            break;
        }
        count++;
    }
}
console.log(prime);

해설

먼저 소수의 정의를 찾아보았다. 소수는 1과 자기 자신으로밖에 나누어 떨어지지 않는 수이다. (1은 소수가 아니다.)

count라는 변수를 만들어 2부터 자기자신보다 작은 수까지 나누어 떨어지는지를 반복하여 확인하여 소수를 판별하였다.

• 현재 제출한 코드는 시간이 180ms 걸리는데,

if(parseInt(num[i]) === 1){   		//1이면 소수가 아니다.    
            break;
}

if문 대신

while(parseInt(num[i])>1)

while문에 조건을 주는 것으로 바꾸어서 실행하였더니 244ms가 걸렸다. while문에 조건을 추가하는 것보다 if문을 쓰는 것이 시간이 단축되는 듯 하다.

• 다른 풀이를 보니 소수인지 판별해야할 수의 제곱근을 검사하여서 시간을 더 단축할 수 있었다. 예) 소수인지 확인하고 싶은 수가 16이라면 Math.floor(Math.sqrt(parseInt(num[i])))를 사용하여 16을 4로 만들어 2부터 4까지만 나누어떨어지는지 확인하여 쉽게 소수를 판별할 수 있다. 4*4는 16이니까!
  (4보다 큰 수는 나누어떨어지지 않을 것을 알 수 있다.)