# Is there a general formula for finding the smallest non-trivial positive divisor of a natural number?

For instance, the smallest non-trivial positive divisor ("sntpd") of $12$ is $2$, the sntpd of $25$ is $5$, the sntpd of $9$ is $3$, etc.

So I'd like to know if there's a formula that given a natural number $n$ ($12$, $25$, and $9$ in the examples) allows me to find its sntpd ($2$, $5$, and $3$ in the examples).

• mathworld.wolfram.com/LeastPrimeFactor.html Jun 8, 2018 at 23:55
• I doubt there is any quick algorithm to do this because factoring the product of two large primes is currently very hard and so if you could detect the lowest factor easily then you could factor these products and solve the RSA problem. Jun 9, 2018 at 1:42
• @CyclotomicField excellent remark.
– Lual
Jun 9, 2018 at 3:52
• @vadim123 thanks so much, the plot in the link made me realize that I can use an alternative solution (statistical analysis) for the main problem I'm solving (finding an asymptotic boundary for a program that deals with primes).
– Lual
Jun 9, 2018 at 3:56