How many prime numbers we need?

Question

If we have some not prime number $n > 1$ we always can make prime factorization. For this operation we need $m$ prime numbers.

Is there any way to prove that for given $n$ we can use no more then $m$ first prime numbers?

P.S. For example to cache first $m$ prime numbers in RAM.

Answer 1

You can find the next higher perfect square and then you need to check only till the greatest prime less than the square root of the nearest greater perfect square you found.

For ex. if the number you want to check is $623$. The next higher perfect square is $625$; $\sqrt {625} = 25$. The greatest prime number less than $25$ is $23$. So to check if $623$ is prime it is enough to check till $23$.

Hope it helps.

Answer 2

We know if $n$ is less than the primorial number $p_{x}\#!$ then $m$ is less than $x$.