Is It Prime — Solution & Editorial

Back to the Problem

Trial division by every number up to √N suffices at this limit (about 10⁶ checks); test 2 separately and then only odd divisors.

Complexity: O(√N)

Watch out: 1 is not prime; and looping to N/2 instead of √N times out.