# Prime numbers and $\sqrt{10301}$

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.

• Basically, You want a prediction Algorithm
– user171358
Oct 19, 2014 at 9:38
• I'm not quite sure what you mean by that. Could you explain? Oct 19, 2014 at 9:40

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.
• That is clever; I should have thought of this. So the argument uses the fact that every composite number $n$ has a factor (and thus a prime factor) $\leq \sqrt{n}$, right? If we methodically go through every prime, and find none, then we know no prime factors $\leq \sqrt{n} \Rightarrow n$ is prime. Oct 19, 2014 at 10:01
use that $101<\sqrt{10301}$ and $10301$ is a prime number