Как сделать мой код менее медленным (JavaScript) - наибольший простой коэффициент

Question

Я намереваюсь найти самый большой простой коэффициент числа n в Javascript. Тем не менее, я думаю, что этот код замедляется или может быть отсортирован, но я не вижу, как это сделать. Суть заключается в отображении последнего элемента массива факторов, что будет самым большим фактором. У кого-нибудь есть подсказки о том, как я мог бы сократить это? Проблема в том, что мой браузер уведомляет меня, что страница слишком долго реагирует на 12-значное число. Должен ли я, возможно, не использовать массив?

function biggest(n) { 
// Makes a list of primes smaller than n 
var primes = [2]; 
for (i=3; i < n ; i++) { 
    var j=0; 
    while (j<primes.length) 
    { var quotient = i/primes[j]; 
    if (quotient !== Math.floor(quotient)) 
      {var hasDivisor = false; 
      j++; 
      } 

     else 
      {var hasDivisor = true; 
      j=primes.length+1; 
      } 

    } 

    if (hasDivisor == false) 
     {primes.push(i);} 
} 


// Makes a list of factors 
var factors = []; 
for (i=0; i<primes.length; i++) { 
    var quotient = n/primes[i]; 

    if (quotient==Math.floor(quotient)) { 

     factors.push(primes[i]);} 
} 
    if (factors.length==0) { 
    factors.push(1); 
} 


    items.push("De biggest factor is "+ factors[factors.length-1] +"!"); 



} 

Answer 1

Вам нужно всего лишь список простых чисел до квадратного корня из п, потому что если п = р * д, один или другой из р или д должен быть меньше квадратного корня от n (за исключением случаев, когда n - идеальный квадрат). И вместо вычисления простых чисел путем итерации по всем возможным делителям, гораздо быстрее использовать Сито Эратосфена; в псевдокоде:

function primes(n) 
    ps := [] 
    sieve := makeArray(2..n, True) 
    for p from 2 to n 
     when sieve[p] 
      append p to ps 
      for i from p*p to n step p 
       sieve[i] := False 
    return ps