[실버] 소수 찾기 (1978번)

문제

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

 

입력

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

 

출력

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

 

내 답안:
const fs = require('fs');
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\\n");

arr = input[1].split(" ").map(Number) ;
let prime = [] ;
let count = 0 ;

arr.forEach(function(x){ 
    for (let i = 2 ; i <= x ; i++ ){
        if (x%i == 0 ) prime.push(i)
    }
    if (prime.length == 1 ) count++
    prime = [] ;
}) ;

console.log(count);

>> forEach안에서 소수를 찾는 for반복문을 작동하고, 소수이면 count++ 처리

>> 각 요소가 소수인지 다 나누어서 확인해보고 count처리하기 때문에 오래걸림

 

내 답안:
const fs = require('fs');
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\\n");

let prime = {} ;
for (let i = 2 ; i <= 1000 ; i++) prime[i] = 1 ; 
for (let i = 2 ; i <= 1000 ; i++){
    if ( prime[i]  === 1 ){
        for (let j = i*i ; j <= 1000 ; j += i){
            prime[j] = 0 ;
        }
    }
}
let arr = input[1].split(" ").map(Number) ;
let count = 0 ; 
arr.forEach(function(x){
    if (prime[x] == 1 ) count++
})
console.log(count) ;

>>다른 사람 답안 참고하여 만들어본 식.. 위에보다 속도 2/3으로 줄음!

>>  prime 객체를 만들어서 소수를 찾을 수 있게 만들어버림

>> 일일이 소수인지 나누어서 확인하지 않아도 됨

>> " for (let j = i*i ; j <= 1000 ; j += i) " 를 통해 i의 배수를 0처리