I have this tiny program for finding largest prime divisor (taken from Code Review Stackexchange and written by user Altinak: https://codereview.stackexchange.com/a/74792):

Here is my try to write it in pseudocode:


// This function takes parameters n and f with 1 <= n and 2 <= f.
// It returns n with f factored out of it.
// Also, if f divides n and if f > h then it replaces h with f

factorize(n, f) {
    if (n < f)
        return n
    while (n mod f == 0) {
        n = n / f
        if (f > highest)
            highest = f
    return n

find(n) {
    highest = 1

    n = factorize(n, 2)
    n = factorize(n, 3)

    if (n >= 5) {
        i = 5
        while (i * i <= n) {
            n = factorize(n, i)
            n = factorize(n, i + 2)
            i = i + 6
    if (n == 1)
        return highest
        return n

But the while loop in the function find is harder than ones I have seen before - its number of iterations aren't easy to calculate before the loop, as the variable n from the condition i * i <= n changes in the loop body.

Right now I feel like I'm stuck and have no idea how to write the loop invariant for this loop, but I will try to think of something. Meanwhile, big thanks in advance for any hints!

  • 1
    $\begingroup$ Start with pre- and post-conditions for factorize(). $\endgroup$
    – greybeard
    Aug 14 at 22:39
  • $\begingroup$ factorize() takes parameters n and f with 1 <= n and 2 <= f. It returns n with f factored out of it, and also, if f divides n and if f > h then it replaces h with f. Smth like this. Should I add it to the post? $\endgroup$ Aug 14 at 22:52
  • $\begingroup$ Added to the post $\endgroup$ Aug 17 at 16:50
  • $\begingroup$ Well. Now it should be easy to state a precondition for the loop. What invariants does the loop keep? $\endgroup$
    – greybeard
    Aug 18 at 1:36
  • $\begingroup$ I believe that I have no idea. Maybe I'm over-complicating it, dunno. $\endgroup$ Aug 18 at 1:44

1 Answer 1


The invariant says that the current value of n is the initial value of n divided by all its factors in the trial sequence 2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31... until i. Some of the numbers in this sequence are not primes, but their factors have been previously processed and simplified, so equivalently, we have n divided by all its prime factors until i.

The number of iterations of the while loop equals the number of elements of the sequence 5², 7², 11², 13², 17², 19²... that do not exceed n[5], n[7], n[11]... respectively, where n[m] denotes the value of n after all factors until m have been removed. So the number of iterations is also the number of elements of the sequence until the highest prime factor.

In addition, the function factorize executes a number of divisions equal to the multiplicity of the prime factor f in the number n. When f is not a prime, the function returns immediately because its factors have already been consumed; the iteration count is the same for the initial and current n.

Hence, the total complexity will be like the sum of the multiplicities of the prime factors of n, plus the highest prime factor.

  • $\begingroup$ Thank you for the answer! What do you mean by (total) complexity? (I understand the 1st and 3rd paragraph, but anything else is over my head, it seems.) $\endgroup$ Aug 18 at 12:03
  • $\begingroup$ @LessnessRandomness: I mean time complexity. $\endgroup$
    – user16034
    Aug 18 at 12:06
  • $\begingroup$ Thank you. But isn't a time complexity a different matter from the loop invariant? (I'm beginner, so apologies for noob questions.) $\endgroup$ Aug 18 at 12:20
  • $\begingroup$ @LessnessRandomness: didn't you ask about the number of iterations ? $\endgroup$
    – user16034
    Aug 18 at 12:32
  • $\begingroup$ I believe that no. Loop invariant is smth completely different - it's a fact that holds before each iteration or smth like this and it is used when proving correctness of the program. My apologies about this misunderstanding. $\endgroup$ Aug 18 at 12:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.