[챌린지] [3일차] 가장 큰 소인수 구하기

어제는 회사일, 집안일로 정신이 없어 문제 풀이 챌린지에 실패했다ㅠㅠ

 

오늘은 가장 큰 소인수 구하기 문제에 막혀서 끙끙대는 중...

 

- 문제 -

어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다.예를 들면 13195의 소인수는 5, 7, 13, 29 입니다.
600851475143의 소인수 중에서 가장 큰 수를 구하세요.

 

- 시도 중인 코드 -

let prime = [];

function findPrime(n){
    let factor = [];
    for (let i = 2; i*i <= n; i++){
        if (n % i === 0){
            factor.push(i);
        }
    }
    for (let i = 0; i <= factor.length; i++){
        for (let j =2; j*j <=factor[i]; j++){
            if (factor[i] % j === 0){
                prime.push(factor[i]);
            }
        }   
    }
    console.log(factor);
    console.log(prime);
}

findPrime(600851475143);

 

계속 답이 맞지 않다고 나온다..ㅠㅠ

 

---

2022.09.02

문제 풀이 완료

 

첫번째 루프를 돌면서 소인수와 그의 배수를 array에 담아주었고,

두번째 루프에서는 배수를 제거하고 소인수만 남기기 위해, factor[i] 값에 대해 factor[0] ~ factor[i-1]를 돌며 나누었을 때 나머지가 0인 값을 splice를 통해 제거해 주었다.

이때, splice를 통해 값을 제거한 후, i 값에서 반듯이 1을 빼주어야 array의 모든 값에 대해 검사할 수 있었다.

예를 들면, [0,1,2,3,4,5]의 length = 6인 array에서 '3'을 삭제했으면, 다음 값인 4의 index가 기존 '3'의 인덱스 값이 된다.

function findPrime(n){
    let factor = [];
    //1번 - n을 2~루트n 값으로 나눴을 때 나머지가 0인 값을 array에 push
    for (let i = 2; i*i <= n; i++){
        if (n % i === 0){
            factor.push(i);
        }
    }
    console.log(factor); //[71, 839, 1471, 6857, 59569, 104441, 486847]

    // 2번 - array에 담긴 값 중에, 소인수의 배수를 제거
    for (let i = 0; i < factor.length; i++){
        let number = factor[i];
        for (let j = 0; j < i; j++){
            if (number % factor[j] === 0){
                for (k =0; k < factor.length; k++){
                    if (factor[k] === number){
                        factor.splice(k, 1);
                        i -= 1; // splice로 array의 element가 잘려나가면, length가 달라지기 때문에, 현재 i 값에서 -1을 해주어야 함
                    }
                }
            }
        }
    } 
    console.log(factor); // [ 71, 839, 1471, 6857 ]
    console.log(Math.max(...factor)); // 6857
}

findPrime(600851475143);

 

참고

how to delete elements in array JS (9 ways)

https://love2dev.com/blog/javascript-remove-from-array/#remove-from-array-splice-value