如何在JavaScript中找到整数的素因数？

沃梦达教程前端问题

2022-01-01 7

How can I find the prime factors of an integer in JavaScript?(如何在JavaScript中找到整数的素因数？)

本文介绍了如何在JavaScript中找到整数的素因数？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我试图找出一个数字的质因数，下面使用了一个Java脚本中的for循环将其记录为‘INTEGER’。我似乎无法让它工作，而且我不确定这是我的JavaScript还是我的计算逻辑。数据-lang="js"数据-隐藏="假"数据-控制台="真"数据-巴贝尔="假">

//integer is the value for which we are finding prime factors
var integer = 13195;

var primeArray = [];

//find divisors starting with 2

for (i = 2; i < integer/2; i++) {
  if (integer % i == 0) {

    //check if divisor is prime
    for (var j = 2; j <= i / 2; j++) {
      if (i % j == 0) {
        isPrime = false;
      } else {
        isPrime = true;
      }
    }

    //if divisor is prime

    if (isPrime == true) {
      //divide integer by prime factor & factor store in array primeArray
      integer /= i
      primeArray.push(i);
    }
  }
}

for (var k = 0; k < primeArray.length; k++) {
  console.log(primeArray[k]);
}

推荐答案

上述答案的效率为O(N^2)。这里有一个复杂度为O(N)的更好的答案。

数据-lang="js"数据-隐藏="假"数据-控制台="真"数据-巴贝尔="假">

function primeFactors(n) {
  const factors = [];
  let divisor = 2;

  while (n >= 2) {
    if (n % divisor == 0) {
      factors.push(divisor);
      n = n / divisor;
    } else {
      divisor++;
    }
  }
  return factors;
}

const randomNumber = Math.floor(Math.random() * 10000);
console.log('Prime factors of', randomNumber + ':', primeFactors(randomNumber).join(' '))

您可以随意筛选重复项！

这篇关于如何在JavaScript中找到整数的素因数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！