Find the greatest factor of a number (other than itself)

Question

What is an optimal way to find the greatest factor of a number (other than itself)? So far, I've got this:

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

This is obviously not so efficient. What are other ways to solve this?

Answer 1

If you know the number is not a prime or even then this should work.

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

It will be slow if the smallest factor is large though

Answer 2

I can propose a O(sqrt(N)) approach where N is the number

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

Just traverse through 2 to sqrt(N),

if N = i*(N/i)
then N/i is the biggest number possible, so break at this point

Answer 3

Your requirement is to remove the smallest prime from "num"

• Testing 2 is ok, than start at 3 till to squareroot(num)
• You should increment by 2
• The result is num / i, not just i (i is the smallest prime of num)

(First I was wrong because I thought you are looking for the greatest prime)

Now a tested version

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 4

First, as indicated by a lot of comments/posts here, you need a fast way of identifying prime numbers. I'll give you the code in C++, but it should be relatively easy to convert to 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;
        }

Now you can easily write a piece of code that generates the next prime number:

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

Next (final) step is to iterate over numbers starting at 2, and when a number is found that divides the input, return the corresponding largest divisor.

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