Question

I'm new to the concept of loop invariant and I'm trying to figure out the loop invariant for a program that returns if an integer is prime and, if not, one possible factorization. My intuition is that as a loop invariant condition we need i in the range [2,floor(sqrt(n))] and then n mod i !=0 implies n is prime

bool IsPrime(int n)
{
    if (n == 1) return false;
    if (n == 2) return true;

    //if n (>2) is prime, it's prime factor is just n
    //if n (>2) is not prime, n=a*b, where both a,b<n and we have either a<sqrt(n) or b<sqrt(n)
    var bound = (int)Math.Floor(Math.Sqrt(n));

    //invariant: 2<=i<=bound and n mod i=0
    int i = 2;
    while (i<=bound) 
    {
        //if n is divisible by some integer smaller than the upper bound it is not prime
        if (n % i == 0)
        {
            Console.WriteLine(" " + n/i);
            Console.WriteLine("x" + i);
            return false;
        }
        i+=1;
    }
    return true;        
}

Could you please tell me if that is enough? I already made many attempts and that's the only statement that holds true for the whole loop until i=floor(sqrt(n)).

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top