소수 출력하는 알고리즘

문제

소수(prime number)는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수입니다. 

다시 말해서 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연 수

 

값 n을 입력했을 때, 소수값들을 나타내라. 

 

풀이

범위 내 모든 숫자 i 에 대해서 {

     1과 i사이에 제수가 있는지를 확인

     있으면 => 소수가 아님

     없으면 => 소수이므로 출력해줌

}

 

function prime_Number(num){

    let arr = [];
    
    if(num == 2){
        arr.push(2);
        return arr; 
    }else if(num == 3){
        arr.push(2);
        arr.push(3);
        return arr;
    }else{
        nextPrime: 
        for(let i=2; i<=num; i++){
            for(let j=2; j<i; j++){
                if(i%j ==0) continue nextPrime; 
            }
            arr.push(i);
        }
    }
    return arr; 
}

let test1 = prime_Number(10);

console.log(test1);

[ 2, 3, 5, 7 ]

다른 풀이

더 간결한 방법으로 풀 수 있는 방법이 없을까 하고 생각을 했고, 다른 알고리즘을 찾아보았다. 

 

제곱근(Math.sqrt) 사용하기

let arr = []; 

function isPrime(num){ 
    if(!num || num === 1) return false; 

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

    }
    return true;
}
let num = 10; 

for(let i =2; i <num; i++){
    let temp = isPrime(i); 
    console.log(temp);
    if(temp != false){arr.push(i)}; 
}


console.log(arr);

시간 복잡도 측면에서는 제곱을 활용하는 것이 더 좋다.