[프로그래머스] 소수 만들기 (javascript)

https://programmers.co.kr/learn/courses/30/lessons/12977

코딩테스트 연습 - 소수 만들기

 

해결방법

1. 인덱스가 다른 3개의 숫자의 합인 number의 약수의 갯수가 2개면 answer +1

 

풀이

function solution(nums) {
    let number = 0;
    let yaksu = [];
    var answer = 0;
    
    for (let i = 0; i < nums.length; i++){
        for (let j = i+1; j < nums.length; j++){
          for (let k = j+1; k < nums.length; k++){
                number = nums[i] + nums[j] + nums[k];
                yaksu = []; 
                for (let s = 1; s < number+1; s++){
                    if (number % s === 0) yaksu.push(s);
                }
                if (yaksu.length === 2) answer++;
            }
        }
    }
    return answer;
}

서로 다른 인덱스의 숫자 3개를 합한 number가 소수인지 판별하기 위해

1부터 number까지의 숫자로 number를 나눴을 때 나누어 떨어지는 숫자만 약수 배열에 넣고

소수라면 1과 자기자신만 들어갔을테니 길이가 2일 때만 answer +1을 하도록 했다

하지만 4중 for문이라 시간복잡도가 크다는 단점이 있어 이를 보완할 수 있는 다른 풀이를 찾아봤다

 

배운 점

1. 소수 판별법 1) 제곱근까지만 계산하기

나는 1부터 number까지 모든 숫자로 약수 여부를 판단했는데 그럴 필요가 없었다

number의 제곱근으로 나누어 떨어지면 number의 제곱근의 배수라는 뜻이기 때문에 1부터 number의 제곱근까지만 

for문을 돌려주면 된다

예를 들어, 16의 제곱근은 4인데 4가 나누어 떨어진다면 4의 배수이기 때문에 소수가 아님을 알 수 있다

 

따라서 제곱근까지만 계산하면 시간을 조금이나마 줄일 수 있다

제곱근까지만 for문을 돌렸을 때 소수이려면 1만 약수 배열에 들어가야 하므로 yaksu.length는 1로 바꾸면 된다

function solution(nums) {
    let number = 0;
    let yaksu = [];
    var answer = 0;
    
    for (let i = 0; i < nums.length; i++){
        for (let j = i+1; j < nums.length; j++){
          for (let k = j+1; k < nums.length; k++){
                number = nums[i] + nums[j] + nums[k];
                yaksu = []; 
                for (let s = 1; s <= Math.sqrt(number); s++){
                    if (number % s === 0) yaksu.push(s);
                }
                if (yaksu.length === 1) answer++;
            }
        }
    }
    return answer;

 

 

4중 for문을 안 만들려면 다음과 같이 소수 판별하는 함수를 따로 만들어주는 방법도 있다

let number = 0;
let yaksu = [];
var answer = 0;

function solution(nums) {
    for (let i = 0; i < nums.length; i++){
        for (let j = i+1; j < nums.length; j++){
          for (let k = j+1; k < nums.length; k++){
                number = nums[i] + nums[j] + nums[k];
                yaksu = [];
                is_prime(number);
            }
        }
    }
    return answer;
}


function is_prime(number){
    for (let s = 1; s <= Math.sqrt(number); s++){
        if (number % s === 0) yaksu.push(s);
    }
    if (yaksu.length === 1) answer++;
}

 

 

2. 소수 판별법 2) 에라토스테네스의 체

 

출처 : 위키백과

에라토스테네스의 체는 2부터 n까지의 자신을 제외한 배수를 제거하다 보면 소수만 남는다는 것이다

 

let number = 0;
let all_number = [];
let answer = 0;
let prime = is_prime(3000);


function solution(nums) {
    for (let i = 0; i < nums.length; i++){
        for (let j = i+1; j < nums.length; j++){
          for (let k = j+1; k < nums.length; k++){
                number = nums[i] + nums[j] + nums[k];
                all_number.push(number)
            }
        }
    }
    answer = all_number.filter(n => prime[n] != false).length;
    return answer;
}


function is_prime(n){
    let arr = [];
    for(let i = 2; i <= n; i++){
        if(arr[i] == false) continue;
        for(let k = i + i; k <= n; k += i){
            arr[k] = false;
        }
    }
    return arr;
}

문제에서 각 원소는 1이상 1000이하로 원소 3개를 뽑았을 때 각각 최대값은의 합은1000+999+998이다

3000으로 잡고 마지막으로 number가 들어 있는 배열을 순회하면서 소수 인지 검증하고 소수인 개수를 출력하면 된다

 

참고 : Level2. 프로그래머스 소수 만들기- JavaScript (tistory.com)

Level2. 프로그래머스 소수 만들기- JavaScript