Sieve of Eratosthenes

Some numbers are very special. They are called prime numbers.

A long time ago, a man named Eratosthenes found a way to find them. He used a list of numbers. First, he picked the number 2. He crossed out every second number after that. Then he found the next number that was not crossed out. He did this over and over. The numbers left at the end are the primes. It is a fast way to find them. This trick is still used today.

Prime numbers are very special. A prime number has only two factors. These are the number 1 and itself.

A Greek thinker named Eratosthenes found a smart way to find them. This method is called a sieve. A sieve is a tool used to strain things.

To use it, write a list of numbers. Start with 2. The number 2 is the smallest prime. Next, cross out all its multiples. You can do this by counting by twos. Then, find the next number not crossed out. This will be 3. Cross out all multiples of 3. Keep doing this for each new prime you find.

When you finish, the numbers left are primes. This way is very fast. It only uses addition to find the answers. You do not need to use division. Some people use a segmented sieve for big lists. This helps computers save memory. It breaks the big list into smaller parts. This makes it easier to work with large numbers.

Prime numbers are the building blocks of math. A prime number is a whole number that has exactly two divisors. These are the number 1 and the number itself. Finding these numbers can be a hard job as numbers get larger. The Sieve of Eratosthenes is a famous way to find them. This method is called an algorithm, which is just a step-by-step way to solve a problem. It is much faster than testing every single number one by one.

To use this sieve, you first create a list of numbers. You start with the number 2 and go up to your chosen limit. The number 2 is the first prime, so you keep it. Then, you cross out all the multiples of 2. You do this by counting up by twos, like 4, 6, and 8. Next, you find the next number that is not crossed out. That number will be 3, which is your next prime. You then cross out all the multiples of 3 by counting in steps of three. You repeat this process for every new prime you find.

This clever idea is very old. It is named after Eratosthenes of Cyrene. He was a Greek mathematician who lived in the 3rd century BCE. We first read about his method in a book by Nicomachus of Gerasa. This book was written in the early 2nd century CE. Nicomachus described the method using odd numbers. Even though it is ancient, the sieve is still very useful today. It is one of the most efficient ways to find small primes.

There are ways to make the sieve work even better. One trick is to start crossing out multiples from the square of the prime. For example, if you are looking at 5, you can start at 25. This works because all smaller multiples were already marked by smaller primes. Another way is to use a segmented sieve. This is helpful when you want to find primes in a huge range. A regular sieve needs a lot of memory to hold a giant list. A segmented sieve breaks the big list into smaller parts to save space.

You can think of the sieve like a kitchen tool. A real sieve strains pasta by letting small water pass through. The math sieve strains numbers by letting composite numbers fall through. The only numbers that stay in the sieve are the primes. This method is special because it only uses addition. You do not need to use hard division to find the answers. It turns a big, messy list into a clean set of primes.

The sieve of Eratosthenes is a famous mathematical algorithm used to find all prime numbers up to a specific limit. A prime number is a natural number with exactly two distinct divisors: 1 and itself. Finding these numbers can be difficult as they become more spread out among larger integers. This method is highly efficient for discovering smaller primes because it identifies composite numbers through a systematic process. Instead of testing each number individually, the sieve works by removing non-prime numbers from a list.

To understand the mechanism, imagine a list of consecutive integers starting from 2 up to your chosen limit, $n$. You begin with the smallest prime, which is 2. You then mark every multiple of 2 in the list, such as 4, 6, and 8, as composite. These are numbers that are not prime. Next, you look for the smallest unmarked number greater than 2, which is 3. You then mark all multiples of 3, such as 6, 9, and 12. You continue this process iteratively. Each time you find an unmarked number, it is guaranteed to be prime. You then mark its multiples until you reach your limit.

There are several ways to refine this process to make it faster. One common optimization is to start marking multiples from the square of the prime. For example, when you reach the prime 5, you can start marking at 25. This works because all smaller multiples, like 10 or 15, were already marked by smaller primes like 2 or 3. Another optimization allows the algorithm to stop early. You only need to continue the process as long as the square of your current prime is less than or equal to $n$. Once the square of the next prime exceeds $n$, all remaining unmarked numbers in your list are prime.

This method has a long history in mathematics. It is attributed to Eratosthenes of Cyrene, a Greek mathematician from the 3rd century BCE. The earliest known written reference to the sieve appears in the book "Introduction to Arithmetic" by Nicomachus of Gerasa. This book was written in the early 2nd century CE. While Nicomachus described a version using odd numbers, the core idea remains the same. The sieve has remained a fundamental tool for mathematicians for thousands of years.

Modern computer science uses different versions of this idea to handle massive numbers. A standard sieve can require a lot of memory if the limit $n$ is very large. To solve this, mathematicians use a segmented sieve. This version divides the range of numbers into smaller segments or "pages." You find the primes in the first segment using the regular method. Then, you use those primes to mark composites in each subsequent segment. This approach significantly reduces the amount of memory needed.

Another variation is the incremental sieve, which can generate primes indefinitely without a set upper bound. It works by interleaving the generation of primes with the generation of their multiples. This allows you to find primes in the gaps between multiples as they appear. While some people confuse this with trial division, they are different. Trial division tests if a number is divisible by primes one by one. In contrast, the sieve of Eratosthenes directly generates the composite numbers. This makes the sieve much more efficient for finding ranges of primes.

In terms of complexity, the sieve is a useful way to benchmark computer performance. The time complexity for calculating primes up to $n$ is $O(n \log \log n)$. This is a very efficient rate of growth. However, the basic algorithm requires $O(n)$ memory to store the list of numbers. This is why segmented versions are so important for large-scale calculations. The sieve remains one of the most important bridges between ancient arithmetic and modern computational number theory.