Let's say you have to find the factors of a number $x$. You check if $x$ is divisible by $2$, and so rule out any multiples of $2$. Then, you go to then next non-multiple of $2$ - $3$. $x$ is not divisible by $3$, so you can rule out any multiples of $3$, and so on and so forth. You move up to the next non-multiple of the already ruled out numbers. Is there a way to prove this?
The second question is if there is a way to prove that a number is not prime (especially for non-Mersenne primes) without actually factoring the number or doing something that would take as long as or longer than factoring the number.