TIFR CSE 2024 | Part B | Question: 7

Question

Consider the following algorithm that takes as input a positive integer $n$.

if (n == 1) {
return "Neither prime nor composite."
}
m=2
while (m < n) {
if (m divides n ){
return "Composite."
}
m=m+1
}
return "Prime."

If $n$ is a number of the form $n=p^{2} q^{3} r^{4}$ where $p, q, r$ are natural numbers greater than 1 , how many times does the while loop in the algorithm run?
In the options below, for any real number $m,\lceil m\rceil$ denotes the least integer greater than or equal to $m$.

• A. The while loop runs at most $\left\lceil n^{1 / 9}\right\rceil$ times for all natural numbers $p, q, r$ greater than one.
• B. The while loop runs at most $\left\lceil n^{1 / 9}\right\rceil$ times only if $p, q, r$ are all distinct.
• C. The while loop runs at most $\left\lceil n^{1 / 9}\right\rceil$ times only if at least two of $p, q, r$ are distinct.
• D. The while loop runs at most $\left\lceil n^{1 / 9}\right\rceil$ times only if $p, q, r$ are distinct primes.
• E. The while loop runs at most $\left\lceil n^{1 / 9}\right\rceil$ times only if $p, q, r$ are distinct primes or distinct prime powers.