Can the Sieve of Eratosthenes have a range?

1.6k Views Asked by At

On internet I found many ways to implement the Sieve of Eratosthenes in most computer languages. The calculation always starts from $2$ and then reaches a target limit.

Can the Sieve of Eratosthenes have a range and find all prime numbers between $1000$ and $2000$?

2

There are 2 best solutions below

0
On

No, since for the sieve to function is has to strike out all numbers in the range which are multiples of primes, including multiples of primes smaller than the range in question. If you started at 1000, where would these primes come from?

2
On

The sieve works by removing multiples of primes. You need to remove multiples of $2$, $3$, $5$ and so on even if you're only looking for primes from $1000$ to $2000$. This means you also need to know all of the primes from $0$ to $1000$ to use the sieve. Thus to find primes from $1000$ to $2000$, you will have to carry out calculations from $0$ to $\sqrt{2000}$ - it's equal to the work required to find primes from $0$ to $2000$.