查找數字的最大因子（本身除外）

Question

找到數字的最大因子（除本身之外）的最佳方法是什麼？到目前爲止，我有這個：

function biggestFactor(num) { 
    if (num % 2 == 0) return num/2; 
    var result; 
    for (var i = 1, m = Math.floor(num/2); i < m; i++) { 
    if (num % i == 0) result = i; 
    } 
    return result; 
} 

greatestFactor(1024); // 512 
greatestFactor(1025); // 205 
greatestFactor(1026); // 513 
greatestFactor(1027); // 79 

這顯然不是很有效。有什麼其他方法可以解決這個問題？

Answer 1

您的要求就是從「編號」

• 測試2是確定的，比3日開始，直到到平方根（NUM）
• 你應該2
• 結果增加去除最小素是num/i，不只是i（i是num最小素）

（首先是我錯了，因爲我想你AR Ë尋找最大素數）

現在測試版

function biggestFactor(num) { 
 
    if (num % 2 == 0) return num/2; 
 
    var stop = Math.sqrt(num); 
 
    for (var i = 3; i <= stop; i += 2) { // = because of prime squares 
 
    if ((num % i) == 0) { // test if integer 
 
     return num/i; // return of smallest prime 
 
    } 
 
    } 
 
    return num; // no int or < 2 
 
} 
 

 
for (var num = 10; num < 40; num ++) { 
 
    console.log(num + ' => ' + biggestFactor(num)); 
 
}

Answer 2

首先，正如很多評論/職位在此間表示，需要確定素數的快速方法。我會給你C++中的代碼，但轉換爲JavaScript應該相對容易。

/** 
* Miller Rabin primality test 
* Returns true if n is probably prime 
* optionally, you can specify a vector of witnesses to test against 
* leave empty if you want the algorithm to randomly generate witnesses 
*/ 
static bool isProbablePrime(ulong n, std::vector<ulong> w) 
     { 
      // easy 
      if(n==2 || n==3 || n==5 || n==7) 
      { 
       return true; 
      } 
      if(n<10) 
      { 
       return false; 
      } 

      // write (n-1) as 2^s * d 
      auto d = n - 1L; 
      auto s = 0L; 
      while(d%2==0) 
      { 
       d/=2; 
       s++; 
      } 

      // witness loop 
      std::random_device rd; 
      std::mt19937 gen(rd()); 
      std::uniform_int_distribution<ulong> dis(1, n - 1); 
      bool nextWitness = false; 
      for(int k=0; k<(w.empty() ? 10 : w.size()); k++) 
      { 
       // random base between 1 and n - 1 
       auto a = w.empty() ? dis(gen) : w[k]; 

       // mod pow 
       auto x = modpow(a, d, n); 

       if(x == 1 || x == n - 1) 
       { 
        continue; 
       } 

       // modular exponentiation with repeated squaring 
       for(auto i=s-1; i>=0; i--) 
       { 
        x = (x * x) % n; 

        // composite 
        if(x == 1) 
        { 
         return false; 
        } 

        if(x==n-1) 
        { 
         // the behaviour of this flag, and the break are meant to emulate a 'continue <loopname>' statement 
         nextWitness = true; 
         break; 
        } 
       } 
       if(!nextWitness) 
       { 
        return false; 
       } 
       nextWitness = false; 
      } 

      // probably prime 
      return true; 
     } 

現在可以很容易地編寫的一段代碼，生成下一個質數：

static ulong nextPrime(ulong p) 
     { 
      p++; 
      while(!isProbablePrime(p)) 
      { 
       p++; 
      } 
      return p; 
     } 

下一頁（最後一步）是迭代開始於2號，並且當數目是發現分割輸入，返回相應的最大除數。

long largestDivisor(long n) 
{ 
    long f = 2; 
    while(f < sqrt(n)) 
    { 
     if(n % f == 0) 
      return n/f; 
     f = nextPrime(f); 
    } 
    return n; 
} 

Answer 3

我可以提出一個O（SQRT（N））的方法，其中N是數

function biggestFactor(num) { 
 
    let result = 1; 
 
    for(let i=2; i*i <=num; i++){ 
 
     if(num%i==0){ 
 
      result = num/i; 
 
      break; 
 
     } 
 
    } 
 
    console.log(result); 
 
    return result; 
 
} 
 

 
biggestFactor(1024); // 512 
 
biggestFactor(1025); // 205 
 
biggestFactor(1026); // 513 
 
biggestFactor(1027); // 79

只是通過2至SQRT（N）遍歷，

如果N = i *（N/i）
則N/i是可能的最大數字，所以在這一點上打破

Answer 4

如果你知道這個數字不是質數，那麼這應該起作用。

function greatestFactor(num) { 
    for (var i = 3; num%i>0;) i+=2; 
    return num/i; 
} 

這將是緩慢的，如果最小的因素是大的，雖然