소인수분해 알고리즘 [ javascript ]

소인수분해 알고리즘 [ javascript ]

반응형

입력된 값 n을 소인수분해하여 배열로 return하는 알고리즘입니다.

const primeFactors = n => { const answer = []; // 2로 나눠지면 계속 나누기 while (n % 2 === 0) { answer.push(2); n /= 2; } // 3부터 루트n까지 나눌 수 있으면 나누기 for (let i = 3; i * i <= n; i += 2) { while (n % i === 0) { answer.push(i); n /= i; } } // 루트n부터 n까지 소수인 경우 처리 if (n > 2) answer.push(n); return answer; }; console.log(primeFactors(10)); // [2, 5] console.log(primeFactors(12)); // [2, 2, 3] console.log(primeFactors(100)); // [2, 2, 5, 5] console.log(primeFactors(987654321)); // [3, 3, 17, 17, 379721] console.log(primeFactors(98942342930478921843840297348120370127)); /* [ 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1882747, 1391042987 ] */

반응형

from http://dalconbox.tistory.com/288 by ccl(S) rewrite - 2021-09-08 07:01:31