proof that $n$ is prime or has prime factor $\leq \sqrt{n}$

Question

apparently my attempt proof is wrong says the chat person will, so can you guys tell me how to fix please :)

Show that any integer $n \gt 1$ is either a prime or has as a factor a prime $\leq \sqrt{n}$

if $n$ is prime that is that.

if $n$ isn't prime it has prime factors $n=p_1 p_2 \dots p_i$

assume $p_1,p_2,\dots,p_i\gt \sqrt{n}$

then $n=\sqrt{n}$ or $n\lt p_1 p_2 \dots p_i$, contradiction!

so $n$ has a prime factor $\leq \sqrt{n}$

Answer 1

We have two cases:

1. If $n$ is prime, then we're done

2. If $n$ is not prime, then we have two cases:

   2.1. If $n$ has a prime factor $p\leq\sqrt{n}$, then we're done

   2.2. If $n$ does not have a prime factor $p\leq\sqrt{n}$, then:

   • $n$ has a prime factor $p>\sqrt{n}$

   • $n$ has a factor $\frac{n}{p}\leq\sqrt{n}$

   • If $\frac{n}{p}$ is prime, then we're done

   • If $\frac{n}{p}$ is not prime, then:

     • Let $q$ be a prime factor of $\frac{n}{p}$

     • $q$ is also a prime factor of $n$, and $q<\frac{n}{p}\leq\sqrt{n}$