How many primes do I need to check to confirm that an integer $L$, is prime?

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?

Solution 1:

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.

Solution 2:

Is my reasoning valid, and, is it possible to reduce the number of primes you'd need to check even more?

Yes, your reasoning is valid. This method of trying to deduce whether a number $N$ is prime by testing for prime factors up to $\sqrt N$ is called trial division.

Solution 3:

With trial division it is enough to check up to the square root. In fact, for three-digit numbers, it suffices to check for divisibility up to 31. So if the number ends in 1, 3, 7, or 9 (so you can rule out divisibility by 2 and 5) and the sum of its digits isn’t divisible by 3 (so it isn’t divisible by 3 either) you need only check for 7, 11, 13, 17, 19, 23, 29, and 31. Eight divisions won’t kill you.

It’s no harder to check for prime powers than primes — if you find a prime factor, just check if it divides the number repeatedly until only 1 is left.

I should note that if you’re doing division by hand, there’s no need to compute an explicit square root — if the quotient is less than the divisor, you’re done.

Solution 4:

If a number $n$ is composite, it will have a prime factor less than $\sqrt{n}$. So when brute force searching the primes for factors, you only need to consider primes up to $\sqrt{n}$ which, at least in your $607$ example, you would only need to check primes less than $~24.6$.

Solution 5:

Another method, that nobody proposes yet, is the search for the power. A prime power $p^n$ will yield a relativly small $n$. Try doing a prime-factorization of $n$ by calculating the square, cube and fifth root. If the result is an integer, try taking the roots of this one until it's a prime. This is then you base of exponentiation.

If you reach a composite number (or can't find any integer root) you are done and can call false.

I know, that calculating reminders and divisions is very easy by hand and taking roots is much harder.