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?


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.
