1
$\begingroup$

It's well-known that the sieve of Eratosthenes, using the first $m$ primes {$p_1, p_2, ..., p_m$}, sifts out all composite numbers up to $(p_m+2)^2$, since every composite $n \lt (p_m+2)^2$ contains (at least) one of the $p_i$ in its factorization and so is caught by the sieve.

A similar observation also gives that the sieve catches all the numbers with at least 3 prime factors up to $(p_m + 2)^3$, those with at least 4 prime factors up to $(p_m + 2)^4$, and so-on.

But in fact it seems to catch even more than this: for example, when we use just $P$ = {2,3} for the sieve, a large portion of the numbers between $(3+2)^2 = 5^2 = 25$ and $5^3 = 125$ with two prime factors happen to get caught as well, but a smaller portion with three prime factors get caught between $125$ and $5^4 = 625$, and an even smaller portion with two prime factors in that range. (I think.) Heuristically, this seems to be just because there are larger prime factors to throw together into the factorization.

Are these statistics known? More precisely,

  • What is the probability that the sieve catches a number with $2$ prime factors in the intervals $[(p_m + 2)^2,(p_m + 2)^3]$, $[(p_m + 2)^3,(p_m + 2)^4]$, etc., or with $3$ prime factors in the intervals $[(p_m + 2)^3,(p_m + 2)^4]$, $[(p_m + 2)^4,(p_m + 2)^5]$, etc., etc.

In general, just how efficient is the sieve of Eratosthenes, beyond the "guaranteed" cases described above? Is there an easy way to characterize all this?

$\endgroup$

1 Answer 1

0
$\begingroup$

With regard to your first question this is possibly a double of here. Your observation is correct and it is at least possible to deduct a heuristic rule for this. I programmed this diligently into Erastothenes algorithm (C programmed) and the result is that it does not increase any significant efficiency since the sieve is extremely efficient from an algorithmic point of view.

About your second question, yes Erastothenes is the most efficient only in certain cases Artin is better. There is massive literature about this test and its modifications.

Hope this answer helps.

Append

your question was about the efficiency of the test within the extended intervals. And what we did is such experiments with the test, and we found that the test is so efficient that you can not even recognize any change in efficiency when extending the intervals. However, you will need to find heuristic rules to exclude certain classes of numbers (lets call them irregulars) such as certain prime powers etc. for every specific extension of the interval. There is no measure of probability or mathematical theorem that gives you a clue how the interval extension in general affects precision. In other words for any type of extension you can find and apply a type of heuristic founded sieve (and this can be mostly easily found) to filter the irregulars, before you apply Erastothenes. We were expecting then that this procedure iteratively applied would improve the Erastothenes test in performance. But the improvement is very insignificant.

$\endgroup$
2
  • 1
    $\begingroup$ It's not clear to me how this addresses the question. $\endgroup$
    – AndrewG
    Commented Jul 2, 2013 at 17:31
  • $\begingroup$ I tried to append a further clarification above. Perhaps that helps. $\endgroup$ Commented Jul 2, 2013 at 19:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .