Recently we found a divide and conquer algorithm over . We have an efficient algorithm for the case where all the elements are in , the set of units.
Our divide and conquer algorithm basically partition the numbers by throwing them into different subgroups. Assume has distinct prime factors , and for simplicity, define . We partition to , where contain all the elements that’s divisible by but not for any . We recursively apply our algorithm to each in and combine the solution.
This gives us a recurrence relation, and the crucial part of the recurrence involves the following function.
Let be the th smallest prime number, and defined as . If we know that and , then we can show that by induction.
First, we would need a small lemma.
Let be real numbers such that non of them is or , then
Proof by induction, basically for any , so this is true when .
We can substitute , and see the result matches.
It’s also useful to bound .
It uses the facts on sum of reciprocals of the primes.
Apply this to the actual algorithm running time analysis, we would get a blow up of the running time for the algorithm.