I recently saw the 1998 horror movie "Cube", in which a character claims it is humanly impossible to determine, by hand without a computer, if large (in the movie 3-digit) integers are prime powers, i.e. they are divisible by exactly one prime number. Naturally I decided to try working this problem by hand on paper.
Firstly, In order to determine if a number is a prime power, I only needed to find one prime factor. For example, $5$ is a prime factor of $555$ (because $555 = 5*111$), but the other factor ($111$), is not divisible by five, so therefore $555$ has more prime factors than just $5$, and $555$ is not a prime power.
I was initially just checking all the prime numbers less than the integer $L$, in order, to see if they were factors of $L$. For 3-digit numbers this usually doesn't take that long, but if $L$ itself is a prime, then you'll end up checking every prime less than $L$.
So, the question becomes: Given an arbitrary integer $L$, if you perform a brute force search, checking every prime number from a list, what is the minimum number of primes you would need to check before you could stop and conclude that $L$ is prime?
I decided to try to narrow down the search space. If I have a prime number $P$, where $\frac{L}{2}<P<L$, then that prime number could not possibly be a factor of $L$, because $2P>\frac{2L}{2}$, or, $2P > L$. Similarly if $\frac{L}{3}<P<L$, then, once again, $P$ could not possibly be a factor of $L$, because $3P > L$, and I've already checked that $2$ is not a factor of $L$, so $2P ≠ L$. You could make this same argument for $\frac{L}{5}, \frac{L}{7}, \frac{L}{11}$, etc.
In other words, I don't need to check every prime number, I just need to check every prime number up to the point where $\frac{L}{P_{n}} < P_{n}$, ($P_{n}$ is the nth prime number) because, at that point, all primes before $P_{n}$ have been ruled out, and since $P_{n} > \frac{L}{P_{n}}$ then $(P_{n})^2 > L$, thus $P_{n}$ is not a factor of $L$. Also, if $P_{n} > \frac{L}{P_{n}}$ then $P_{n + 1} > \frac{L}{P_{n + 1}}$, because $P_{n + 1} > P_{n}$, this same reasoning rules out all larger primes.
So, for example, when trying to find a prime factor of $607$, rather than checking every prime number less than $607$, I only need to check the first $10$ primes up to $29$, because $\frac{607}{29} < 29$. If the first $10$ primes are not factors of $607$, then $607$ has no prime factors and must be prime.
Is my reasoning valid, and, is it possible to reduce the number of primes you'd need to check even more?
Best Answer
A composite number is always at least as big as the square of its least prime factor. So if a number is composite, it will have a factor no larger than its square root, as you have shown.
Examples like $289=17 \times 17$ show that you can't do better than this. With different prime factors you can take something like $29\times 31 = 899$ and you can't do better.
The second example - which is not a prime power - depends on primes being close together - although the twin prime conjecture (infinitely many pairs of primes with difference $2$) is still open, there are now known to be infinitely many pairs of primes with small differences.
The claim you quote, that checking three digit numbers to see if they are prime powers is difficult is frankly ludicrous. I can do that fairly efficiently in my head. There are not many prime squares, and beyond that the powers of $2,3,5,7$ are not difficult to identify.