Suppose we want to find all the prime numbers between 2 and n. The brute force approach to this problem is to iterate through all the numbers in the range and check if that number is prime or not using the approach discussed in this blog.
The time complexity of this approach is O(n*sqrt(n)). We can do better. We are not making use of the already processed numbers. For example, suppose we conclude that a number x in our range is prime by some method, then we are sure that all the multiples of x in our range are not prime numbers. Using pre-computed prime numbers to eliminate its multiples in the range is known as the Sieve of Eratosthenes.
This algorithm finds all primes numbers from 2 to n. We assume that all the numbers in this range are prime at the start, i.e. mark them as potential candidates for prime numbers. In the following steps, we look at the first marked number, considering this to be a prime number. Then we unmark all the multiples of this number in our range, as we are sure that those numbers are not prime numbers. As the prime factors of a number are bounded by sqrt(n), we can limit our iterations to sqrt(n) starting from 2.
We will start from 2 [first marked number] and unmark all the multiples of the 2 till 100.
Then we start with 3 (the next marked number) and unmark all multiples of 3 till 100.
Similarly, do this for 5 and 7 as they are marked numbers less than sqrt(100). After this, the marked numbers are the prime numbers from 1 to 100.
To remove the composite numbers, we unmark the multiples of the current prime number. Now let us assume our current prime number is 2. In the first iteration, we will unmark n/2 elements. When our current prime number is 3, we unmark n/3 numbers. The total number of times we run the loop would be equal to:
n/2 + n/3 + n/5 + n/7 + n/11 + ……
= n*( 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ……)
Using Harmonic Progression of the sum of primes, it can be proved that:
( 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ……) = log(log(n))
Therefore, the total time complexity of the Sieve of Eratosthenes algorithm is O(nlog(log(n))).
The segmented sieve algorithm is also used to find all prime numbers from 1 to n or all the primes in a given range. A segmented sieve is an optimization in memory usage over a simple sieve, which makes it helpful in finding primes from 1 to n efficiently compared to a simple sieve. We divide the range from 1 to n into smaller segments, and we find the prime numbers for those segments separately. The division of the whole range into segments allows us to keep one segment in memory at a time instead of loading the entire range into memory.
Algorithm Idea
The time and space complexity for the segmented sieve is the same as that of the simple sieve.
Finding primes in a range: Sometimes we need to find all prime numbers in a range [l, r] of small size (r -l + 1 <= 10⁵), but l and r can be very large(10¹²). To solve such problems, we use the idea of the Segmented sieve. We generate all prime numbers up to sqrt(r) and use those primes to mark all composite numbers in the segment [l, r]. Explore and think!
Enjoy learning, enjoy mathematics, enjoy algorithms!
There are n+1 people at a party. They might or might not know each other names. There is one celebrity in the group, and the celebrity does not know anyone by their name. However, all the n people know that celebrity by name. You are given the list of people present at the party. And we can ask only one question from each one of them. “Do you know this name”? How many maximum numbers of questions do you need to ask to identify the actual celebrity?
Given a positive integer n, write a program to check if the number is prime or not. A number n > 1 is said to be a prime number if 1 and n are its only factors. In other words, a prime number is a number that is divisible only by two numbers itself and one.
The summation formulas are used to calculate the sum of the sequence. In this blog, we have discussed the visual proofs: the sum of numbers from 1 to n (arithmetic series), the sum of infinite geometric series, the sum of squares of numbers from 1 to n, etc.