양의 정수를 여러 소인수로 분해하는 과정을 소인수 분해라고 합니다.
간단한 예:
24의 소인수는 2*2*2*3이며 이를 (2^3) * (3^1)로 축약합니다.
컴퓨터의 경우 해시 테이블을 사용하여 이 결과를 저장할 수 있으며 JS에서는 다음 형식으로 표현할 수 있습니다.
{ '2': 3, '3': 1 }
그럼 어떻게 소인수를 분해할 수 있을까요?
먼저 소수인지 판단할 방법이 필요합니다.
function isPrime(n){ for(var i=2;i<=Math.sqrt(n);i++){ if(n % i == 0){ return false; } } return true; }
그런 다음 짧은 나눗셈을 사용하여 분해합니다.
function PrimeFactorizer(n){ //用来存储结果的hash var hash = {}; while(n > 1){ //从最小的质数开始除 for(var i=2;i<=n;i++){ if(isPrime(i) && n % i == 0){ //如果hash中有这个质数,则存储的数目+1 if(hash[i]){ hash[i] = hash[i] + 1; }//否则把该质数作为key,value为1 else{ hash[i] = 1; } //除掉这个最小的质数因子 n /= i; } } } //给实例上加个factor属性 this.factor = hash; hash = null; } new PrimeFactorizer(24).factor // { '2': 3, '3': 1 }
위는 흥미로운 JavaScript 질문입니다. 소인수 분해에 대한 자세한 내용은 PHP 중국어 웹사이트(www.php.cn)를 참고하세요!