-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) ?

$\endgroup$
  • 1
    $\begingroup$ Sorry, but this is incomprehensible. $\endgroup$ – Gerry Myerson Aug 9 '11 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 '11 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 '11 at 17:38
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.)

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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