如何在Javascript中使用for循环查找素数因子？

Question

我是javascript的新手,并试图找到一个数字的素数因子,在javascript中使用for循环记录下面为'整数'.我似乎无法让它工作,我不确定这是我的JavaScript还是我的计算逻辑.我尝试添加注释,以便您可以看到我认为我的程序当时正在做什么.如我错了请纠正我.

任何帮助将不胜感激.这是我的代码:

//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]);
}

Answer 1

上面的答案在O（N ^ 2）复杂度方面效率低下。这是O（N）复杂度的更好答案。

function primeFactors(n){
  var factors = [], 
      divisor = 2;

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

您可以根据需要过滤重复项！

Answer 2

我确实认为上面两个代码都有错误.如果将整数替换为100,则素数因子化将不再起作用,因为因子2不能与循环的因子2一起考虑.当j = 2时,i = 2且j <= i/2处于条件状态 - 意味着循环将永远不会运行i = 2,这是一个主要因素.

试图让它以这种方式工作,但无法弄清楚.

不得不依赖于一个while循环的不同方法:

    function getAllFactorsFor(remainder) {
    var factors = [], i;

    for (i = 2; i <= remainder; i++) {
        while ((remainder % i) === 0) {
            factors.push(i);
            remainder /= i;
        }
    }

    return factors;
}

https://jsfiddle.net/JamesOR/RC7SY/

你也可以用这样的东西:

let findPrimeFactors = (num) => {
    let arr = [];


    for ( var i = 2; i < num; i++) {
        let isPrime
        if (num % i === 0) {
            isPrime = true;
            for (var j = 2; j <= i; j++) {
                if ( i % j === 0) {
                isPrime == false;
                }
            } 
        }if (isPrime == true) { arr.push(i)}

    }console.log(arr)
}

findPrimeFactors(543)

Answer 3

这是一个有效的解决方案:

//integer is the value for which we are finding prime factors
var integer = 13195,
    primeArray = [],
    isPrime;

//find divisors starting with 2

for(i = 2; i <= integer; 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 the 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]);
}

你走在正确的轨道上.有两个小错误.评价integer - 1似乎是不正确的.我相信<= integer在你的外for循环中更合适的评估.这是因为当你将下面的整数除以下时integer /= i,这将导致最终的整数评估29.在这种情况下,最终的除数也是29如此,因此需要进行评估,<=以反对< integer - 1.

至于为什么最终的日志声明不起作用,有一个简单的错字primeArray[i]反对primeArray[k].

Answer 4

我们只需一个循环就可以找到 n 以内的质因数。这是一个非常简单的解决方案，没有任何嵌套循环。

时间复杂度将小于 O(n)，因为我们将“n”除以“i”。

function primeFactors(n) {
    let arr=[];
    let i = 2;
    while(i<=n){
        if(n%i == 0) {
            n= n/i;
            arr.push(i);
        } else {
            i++;
        }
    }
    return arr;
}
// primeFactors(10) [2,5]
// primeFactors(10) [2,2,5,5]
// primeFactors(2700) [2, 2, 3, 3, 3, 5, 5]