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

Question

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}

\\frac{2L}{2}$, or, $2P > L$. Similarly if $\\frac{L}{3}

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?

Answer 1

Typically the half way point is the cut-off. If you do not find a prime divisor by then, there are none.

Since your bound is already lower than that, it is optimized