CODEWITHSUNDEEP
algorithmlanguage-agnosticfactorization
Kevin
Kevin

Reputation: 2697

How does this method, which finds the smallest factor of a given number, work?

I've recently come across a method which returns the smallest factor of a given number:

public static int findFactor(int n) 
{
    int i = 1;

    int j = n - 1;

    int p = j; // invariant: p = i * j

    while(p != n && i < j) 
    {
        i++; 
        p += j;

        while(p > n) 
        {
            j--; 
            p -= i;
        }
    }

    return p == n ? i : n;
}

After examining the method, I've been able to (most likely incorrectly) determine the quantities which some of is variables respectively represent:

n = the int that is subject to factorization for 
    the purposes of determining its smallest factor

i = the next potential factor of n to be tested

j = the smallest integer which i can be multiplied by to yield a value >= n

The problem is I don't know what quantity p represents. The inner loop seems to treat (p+=j) - n as a potential multiple of i, but given what I believe j represents, I don't understand how that can be true for all i, or how the outer loop accounts for the "extra" iteration of the inner loop that is carried out before the latter terminates as a result of p < n

Assuming I've correctly determined what n, i, and j represent, what quantity does p represent?

If any of my determinations are incorrect, what do each of the quantities represent?

Upvotes: 1

Views: 242

Answers (2)

user1196549
user1196549

Reputation:

The algorithm tries all divisors between 1 and n / i (continuing past n / i is of no use as the corresponding quotients have already been tried).

So the outer loop actually performs

i= 1
while i * (n / i) != n && i < n / i)
{
  i++;
}

It does it in a clever way, by avoiding divisions. As the annotation says, the invariant p = i * j is maintained; more precisely, p is the largest multiple of i that doesn't exceed n, and this actually establishes j = n / i.

There is a little adjustment to perform when i is incremented: i becoming i + 1 makes p = i * j become (i + 1) * j = p + j, and p may become too large. This is fixed by decrementing j as many times as necessary (j--, p-= i) to compensate.

Upvotes: 1

mindriot
mindriot

Reputation: 5678

p stands for “product”. The invariant, as stated, is p == i*j; and the algorithm tries different combinations of i and j until the product (p) equals n. If it never does (the while loop falls through), you get p != n, and hence n is returned (n is prime).

At the end of the outer while loop's body, j is the largest integer which i can be multiplied by to yield a value ≤ n.

The algorithm avoids explicit division, and tries to limit the number of j values inspected for each i. At the beginning of the outer loop, p==i*j is just less than n. As i is gradually increased, j needs to gradually shrink. In each outer loop, i is increased (and p is corrected to match the invariant). The inner loop then decreases j (and corrects p) until p is ≤ n again. Since i*j is only just less than n at the beginning of the next outer loop, increasing i makes the product greater than n again, and the process repeats.

Upvotes: 4

Related Questions