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)