Loop invariant condition IsPrime program
-
05-11-2019 - |
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