I am trying to understand if it makes sense an algorithm to decide if a given number $n$ is possibly prime or not by using the divisor function bound defined by professor Jeffrey Lagarias as:
$\sigma(n)\lt H_n + ln(H_n)e^{H_n}$
where $H_n$ refers to the Harmonic number.
The idea for the algorithm is as follows:
A given number $n$ is possibly prime if and only if when picking up randomly $K$ integers in the interval $[2..\lfloor n/2\rfloor]$ no one of them divides $n$.
The question is:
How many pickups $K$ should I do so I could have a $p$% of probability of picking up a divisor of $n$ (if exists) in the $[2..\lfloor n/2\rfloor]$ interval?
For instance, $p$% = $80$%.
My idea is that assuming the existing bound for $\sigma(n)$, the probability of finding a factor / divisor of $n$ in $[2..\lfloor n/2\rfloor]$ would be:
$P_n = \frac{H_n + ln(H_n)e^{H_n}}{(n/2)-2}$
But from that point I do not know how to continue... does it makes sense a possibly prime algorithm like this one or not? any ideas or comments regarding the topic are very welcomed.
This will not be an efficient algorithm for most interesting numbers. The amount of divisors of $N$ below $N$ can be very small. Say for numbers you care about in RSA you have exactly two divisors of $N$.
Even for very smooth numbers you will be much more likely to pick a non divisor then a divisor. The most problematic issue with your algorithm though is that your bound for $\sigma(n)$ is from the wrong side. You will want to bound your probability of failure (failing to say composite when the number is composite) from below. I.e. you want to be at least $p_K$ sure that $n$ is composite where $K$ is number of attempts and $p_K$ is some probability which goes to 1 as $K$ goes to $\infty$. Since your bound on the number of divisors is from above though you can't bound the probability from below. What you would need is that there is at least some amount of divisors of $N$ below $N$ so that when choosing numbers randomly you choose a divisor with probability at least $p$ since there are at least bound many divisors. But instead you know that there are at most $H_n+\ln(H_n)e^{H_n}$ divisors which only gives you an upper bound on the probability instead of a lower bound.
Hope that makes sense.