-1
$\begingroup$

I have developed an algorithm, Sieves like, that only pick every integer once. The Sieve algorithm of course selecting integers in as many iterations as the integer has distinct prime factors.

Is this seen before (I haven't found it) ?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Sorry, but this is incomprehensible. $\endgroup$
    – Gerry Myerson
    Aug 9, 2011 at 12:48
  • 1
    $\begingroup$ Have you compared with Pritchard's wheel sieve? ams.org/mathscinet-getitem?mr=685983 $\endgroup$
    – François G. Dorais
    Aug 9, 2011 at 15:55
  • $\begingroup$ Thank you François, That was what I meant, and I will look at Pritchard's wheel to compare. Sorry if my question was difficult to comprehend. Jorgen $\endgroup$
    – Jorgen
    Aug 9, 2011 at 17:38

1 Answer 1

Reset to default
1
$\begingroup$

It may interest you that the asymptotically fastest prime sieve (of Atkin-Bernstein) spends less than unit time on each number in the interval, by considering increasingly thin congruence classes as its input increases. (Of course it spends positive time, $O(\log n/\log\log n)$, on each prime.)

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks Charles! However I'm looking for beauty - not speed :-) Jorgen $\endgroup$
    – Jorgen
    Aug 10, 2011 at 6:48
  • $\begingroup$ It may be related to the classical sieve of Sundaram, q.v. $\endgroup$
    – Charles
    Aug 10, 2011 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.