MathDB
Mary's claim to fame [Baltic Way 2003]

Source:

November 7, 2010
ceiling functionnumber theory proposednumber theory

Problem Statement

All the positive divisors of a positive integer nn are stored into an increasing array. Mary is writing a programme which decides for an arbitrarily chosen divisor d>1d > 1 whether it is a prime. Let nn have kk divisors not greater than dd. Mary claims that it suffices to check divisibility of dd by the first ⌈k2⌉\left\lceil\frac{k}{2}\right\rceil divisors of nn: dd is prime if and only if none of them but 11 divides dd. Is Mary right?
Back to ProblemsView on AoPS