Prime numbers and $\sqrt{10301}$

Question

On my exam recently, we had the following question:

Use the prime number theorem to estimate the number of primes less than $\sqrt{10301}$, and hence, give a concise argument whether 10301 is prime or not.

I answered as best I could, using the estimate $\frac{\sqrt{10301}}{\ln{\sqrt{10301}}}$, which is about 22. I think there are about 25 primes but whatever. As for the next part of the question, how could I "concisely" argue that 10301 is prime? I know that $n$ prime $\Rightarrow \sqrt{n}$ is irrational, but obviously the converse is not necessarily true. I threw it down anyways. Short of saying "the only two factors of 10301 are 1 and 10301", but that's not an argument. How does $\sqrt{10301}$ come into play here? Thanks in advance for help.

Answer 1

By definition, any factor $p$ of a natural number $N$ has a complement, that is, a natural number $q$ such that $N = pq$. Now, one of $p, q$ must be $\leq \sqrt{N}$ (if not, we would have $N = pq > \sqrt{N} \cdot \sqrt{N} = N$, a contradiction), so to check whether $N$ prime, it is enough to show that it has no factors $\leq \sqrt{N}$. Any factor itself has a prime factor, so in fact it suffices to check whether $N$ has any factor among the primes $p \leq \sqrt{N}$.

So, the quantity $$\frac{\sqrt N}{\ln \sqrt N} \sim \# \{p \text{ prime}: p \leq \sqrt N\}$$ you computed for $N = 10301$ is an estimate of how many primes you need to check to determine that $N$ is prime (which in this case it is). Whether checking $\sim 22$ (actually $26$) primes manually is "concise" is up for debate.

Answer 2

use that $101<\sqrt{10301}$ and $10301$ is a prime number