# Re: Another binary search time complexity (a fraction of previous subset)

On 2011-02-24, pamela fluente <pamelafluente@xxxxxxxxx> wrote:
Now the fact that one could possibly have in ( P(i), P(i+1) ) a
composite which is a product of 2 previous prime, say PA * PB, means
as you say it will not be eliminated until the step where i get to
remove the multiples of the min(PA, PB).

At that point i have done log( min(PA, PB) ) steps (steps are
performed one for each previous prime).

No, since there are about (N/log N) primes less than N, not O(log N).
With the 10^100 example, min(PA, PB) could be quite close to 10^50,
and there are about 10^48 primes to test.

The number of operations grows only very slightly slower than
O(sqrt(N)).

--
Tim
.

## Relevant Pages

• Re: Another binary search time complexity (a fraction of previous subset)
... composite which is a product of 2 previous prime, say PA * PB, means ... No, since there are about (N/log N) primes less than N, not O. ... The number of operations grows only very slightly slower than ... Thanks a lot Tim. ...
(comp.theory)
• Re: Divisibility of (p-1)......(p-i+1)
... But p is visible by q, so p-=k too (as a difference of two multiples of q). ... hence q is less or equal to k<i, a contradiction since i is the smallest prime factor of p. ... Best regards, ...
(sci.math)