Question 109
All the positive divisors of a positive integer $n$ are stored into an array in increasing order. Mary has to write a program which decides for an arbitrarily chosen divisor $d\gt 1$ whether it is a prime. Let $n$ have $k$ divisors not greater than $d$. Mary claims that it suffices to check divisibility of $d$ by the first $\lceil k / 2\rceil$ divisors of $n$ : If a divisor of $d$ greater than 1 is found among them, then $d$ is composite, otherwise $d$ is prime. Is Mary right?