Check if a Number Is Prime / Integer Square Root

Problem Two number-theory routines. First, test whether an integer n is prime as efficiently as possible. Second, compute the integer square root of n (floor(sqrt(n))) without using floating-point arithmetic.

Input / Output

• Input: a non-negative integer n.
• Output: for primality, a boolean; for integer square root, the largest integer r with r*r <= n.

Constraints

• n up to 10^12 — beware overflow when squaring candidates.
• No floating point for the square root (avoid precision error near perfect squares).

Example

• isPrime(97) -> true; isqrt(50) -> 7 (since 7*7=49 <= 50 < 64).