L6. Sieve of Eratosthenes | Maths Playlist
Summary
TLDRIn this video, the instructor explains an optimized algorithm for finding prime numbers up to a given number using the Sieve of Eratosthenes. The initial brute force method is discussed, followed by the introduction of the sieve algorithm, which significantly reduces time complexity by precomputing prime numbers. The video covers the step-by-step process, explains the logic behind eliminating non-prime numbers, and introduces optimizations to further enhance efficiency. Finally, the video provides insights into the time and space complexities of the algorithm, offering helpful code implementation tips.
Takeaways
- 🧮 The problem involves finding all prime numbers up to a given number, 'n'.
- ⚙️ The brute force method has a time complexity of O(n * √n), which is inefficient for large values of 'n'.
- ⏱️ The optimized solution uses the Sieve of Eratosthenes algorithm, which improves time complexity by precomputing prime numbers.
- 🔢 The key idea is that for any prime number, all its multiples are not prime and can be marked as non-prime.
- 🟢 The algorithm works by creating an array of size 'n+1', marking 1 for prime candidates and 0 for non-prime numbers.
- ✖️ Once a prime is identified, all its multiples are marked as non-prime starting from the prime squared.
- 🚀 The optimized time complexity of the algorithm is O(n log log n), thanks to precomputation and the efficient marking process.
- 📝 The sieve only needs to loop up to the square root of 'n', reducing unnecessary computations for larger values.
- 🧠 The space complexity is O(n) because of the additional array used to store the prime status of each number.
- 📈 This approach is highly efficient for large values of 'n', and the precomputation step is the key to optimizing prime number checking.
Q & A
What is the problem the speaker is trying to solve?
-The problem is to print all prime numbers up to a given number 'n'. For example, if n = 10, the prime numbers up to 10 are 2, 3, 5, and 7.
What is the brute force solution mentioned for finding prime numbers up to n?
-The brute force solution involves iterating through all numbers from 2 to n and checking each number to see if it's prime by dividing it by all numbers up to its square root. This method has a time complexity of O(n√n).
Why is the brute force solution inefficient for large values of n?
-The brute force solution is inefficient because for large values like n = 10^5 or 10^6, the time complexity grows significantly, leading to an enormous number of operations, making the algorithm slow.
What is the optimized approach introduced in the script?
-The optimized approach introduced is the Sieve of Eratosthenes, an algorithm that marks the multiples of each prime number as non-prime. This allows prime numbers to be determined in constant time after some initial precomputation.
How does the Sieve of Eratosthenes algorithm work?
-The algorithm works by creating an array where all numbers are initially marked as prime. Starting from the first prime (2), it marks all multiples of 2 as non-prime, then moves to the next number (3), marking all its multiples, and so on. This process continues until all numbers are either marked as prime or non-prime.
What is the time complexity of the Sieve of Eratosthenes?
-The time complexity of the Sieve of Eratosthenes is O(n log log n), which is much more efficient than the brute force method.
How does the Sieve of Eratosthenes avoid unnecessary computations?
-The algorithm avoids unnecessary computations by starting from the square of each prime number when marking multiples, as smaller multiples would have already been marked by earlier primes. Additionally, it only processes numbers up to the square root of n, as larger numbers are already covered.
What space complexity does the Sieve of Eratosthenes have?
-The space complexity of the Sieve of Eratosthenes is O(n), as it requires an array of size n to store whether each number is prime or not.
What optimizations are suggested for the Sieve of Eratosthenes?
-The two main optimizations are: 1) starting to mark multiples from the square of each prime number to avoid redundant work, and 2) stopping the outer loop once it reaches the square root of n, as no further marking is necessary beyond that point.
What is the role of precomputation in the Sieve of Eratosthenes?
-Precomputation plays a critical role in the Sieve of Eratosthenes by calculating which numbers are prime in advance. Once this precomputation is done, determining whether any given number is prime can be done in constant time, O(1).
Outlines
🔢 Introduction to Prime Number Algorithm and Basic Brute Force Approach
In this section, the speaker introduces a problem related to prime numbers, explaining the task of finding all prime numbers up to a given number n. The example provided uses n = 10, where the prime numbers are 2, 3, 5, and 7. The speaker presents a brute force solution where, for each number, they check if it is prime by iterating from 2 to n and using a prime-checking function. The brute force method has a time complexity of O(n √n), making it inefficient for larger values of n, such as 10^6. The speaker suggests optimizing this approach by reducing the prime-checking time to constant time, which leads into a more efficient algorithm.
⚙️ Optimizing Prime Checking with Sieve of Eratosthenes
The speaker introduces the Sieve of Eratosthenes, an algorithm that optimizes prime-checking by marking non-prime numbers efficiently. To illustrate, an array is initialized where all values are set to 1 (indicating prime). Starting from 2, the first prime, the algorithm marks all multiples of 2 as 0 (non-prime). This process continues for the next prime, 3, and its multiples. The algorithm ensures that each prime’s multiples are marked as non-prime without checking numbers already marked by smaller primes. This way, a black box is created where checking whether a number is prime becomes a constant-time operation.
📉 Optimizing the Sieve Further: Avoiding Redundant Marking
The speaker discusses how to further optimize the Sieve of Eratosthenes by starting from i^2 instead of i × 2 when marking multiples of each prime i. The rationale is that smaller multiples of i would have already been marked by smaller primes. For example, for i = 5, there’s no need to mark 5 × 2 = 10, as it would have been marked when processing 2. By starting from i^2, the algorithm avoids unnecessary computations and increases efficiency. Additionally, the speaker introduces the idea of limiting the loop to √n, as numbers beyond that would have their multiples already marked.
⏱ Final Optimizations and Complexity Analysis
In the final part, the speaker explains the time complexity of the optimized Sieve of Eratosthenes. The marking process runs in O(n log log n), which is more efficient than the brute force approach. The space complexity remains O(n), as it uses an array to store the primality of each number. The speaker reiterates the process, emphasizing that the algorithm performs precomputation to ensure that checking whether a number is prime takes constant time. The video concludes by encouraging viewers to like, subscribe, and check out the code implementations for different programming languages.
Mindmap
Keywords
💡Prime Numbers
💡Brute Force
💡Time Complexity
💡Space Complexity
💡Optimization
💡Sieve of Eratosthenes
💡Precomputation
💡Multiples
💡Array
💡Mathematical Proof
Highlights
Introduction of prime number algorithm with time complexity issues and why brute force is inefficient.
Explanation of the Sieve of Eratosthenes algorithm, focusing on optimizing prime number checks.
Example given with number n=10, demonstrating how to find all prime numbers up to n.
Brute force method discussed with time complexity O(n * sqrt(n)), showing its limitations for larger numbers like 10^6.
Key insight: Multiple of a prime number will never be prime, and marking these multiples can optimize prime detection.
Detailed steps in the Sieve of Eratosthenes: initializing an array with 1s, marking non-prime numbers as 0.
Discussion on starting at 2, the first prime, and marking all multiples of 2 (e.g., 4, 6, 8, etc.) as non-prime.
Moving to the next prime, 3, and repeating the marking process for all multiples of 3.
Prime number identification based on the array values: all remaining 1s represent primes.
Optimization: No need to mark multiples of numbers like 4, 6, 8, since they are already marked as non-prime by smaller primes.
Further optimization: Instead of starting from i * 2, start from i * i to reduce redundant operations.
Explained the importance of stopping the loop once i * i exceeds the number n, as further calculations are unnecessary.
Introduction of the time complexity analysis of Sieve of Eratosthenes, revealing O(n log(log(n))).
Final optimized pseudo code presented, including marking non-prime numbers efficiently.
Conclusion with a discussion on space complexity, which is O(n) due to the array used for prime detection.
Transcripts
so let's continue with the math section
in sters A to Z DSA course but before
that here you welcome back to the
channel I hope you guys are doing
extremely well so the problem that we
will be solving today is C of AAS cross
tees something like that so this uh
algorithm is something which is related
to prime numbers so in order to
understand that let's pick up a very
simple problem given a number n we have
to print all the primes up till n so
assume I give you n as 10 so I have to
print out all the Primes till the number
10 so that will be 2 3 5 and 7 so there
are four Prime till then you'll have to
print down all the four prime numbers
now what is the extreme name solution
that you can think of we know how to
check a prime number right so it'll be
like okay start from I equal to 2
because that is the first prime number
we can go ahead till n and we can call
the prime function that we already know
how to write if this is a prime number
we can print the prime so this will be
the extreme name solution The Brute
Force and what will be the D complexity
the outer loop is running for B go of N
and the prime check we know can be done
in square root of n so this will be the
time complexity will there be any space
complexity no the space complexity will
be we go of one obviously this is an
extremely expensive operation why
imagine I give you n as 10 to the^ 5 and
I ask you to print down all the prime
numbers till 10 ^ 5 then the time
complexity will be B go of 10^ 5 into
square root of 10^ 5 which is a lot of
time and if I give you 10^ 6 then that's
a lot of operations right so that is why
this method is something that we will
not be following and we'll try to
optimize this so what will be the
optimized method so what is taking time
over here the first one is the loop
which is hydrating through each and
every integer and then there is a prime
check if I can optimize this Prime check
and if I can do it in a constant time if
I can do the prime check in a constant
time then the square root of n will go
off and that is what I will be trying to
do and that is where this particular
algorithm see of era TOS things or
something like that comes in so what I
will try to do is I'll try to create a
black box where if I pass on an integer
it tells me if it is a prime or not but
this black box will be working in beo of
one time complexity so in order to do
that what I'll be doing
is I'll be taking Nal 30 just to explain
you what algorithm I'm thinking of like
what is the black box that that I'm
thinking of Nal to 30 I'll be declaring
a prime array of 31 size that is one
more than the number okay and I started
the index from two I've omitted the
zeroth index and the first index because
I know that these numbers are never
Prime like one is not a prime number so
it'll be starting off at two so to start
of what I've done is I've initialized
everything with one all the indexes with
one till the last index which is 30
start from the second index till the
30th index everything is one okay now
the start of what I'll do is I'll start
with the number two and I know that two
is a prime number that is for sure
because that is the first Prime I'm very
sure can I say this if 2 is prime any
multiple of two will never be prime
something like 2 into 2 which is 4
that's never going to be prime because
it has a factor two 2 into 3 that is 6
will never be prime because it has a
factor two for a number to be prime the
factors can only be one and the number
itself so obviously two is a factor so
it cannot be a prime 2 into 4 8 2 into 5
10 these numbers cannot be prime I'm
very sure of it so what I'll do is I'll
be like okay let's go ahead and mark
them as zero so I'll go ahead and mark
them as zero
perfect 0 0 0 0 0 0 0 0 and zero so I've
marked every multiple of two as zero
till the number that is 30 done so 2 is
completed what is the next number three
again do the same thing I'll be like
okay three is a prime number how do I
know it because it is marked as one it
is marked as one didn't get a factor
before okay fine so what's 3 into 2
that's 6 what's 3 into 3 that's 9 so be
marking all the multiples of three
starting from 6 till 30 as zero let's do
it so six is already marked as Z 9 will
be marked as 0 12 is already marked 15
will be marked as 0 18 is already marked
21 will be marked as 0 24 will be marked
as 0 27 will be marked as 0 30 is
already marked as 0 so 38 is done what
is the next number the next number is
four tell me one thing is four a prime
no it is not because it is already
marked as zero which means someone
marked it two did Mark it that means it
is a multiple of two tell me one thing
what are the multiples of
four that's eight that's three that's
16 all the multiples of four will also
be multiples of two agreed basic maths
all the multiples of four will be
multiples of two as well so do I need to
go ahead and Mark 8 12 16 I do not
because it is a non- prime number got it
so not do anything I'll go to the next
number which is five for five is it a
prime it is because it is marked as one
it didn't find any factor or before it
so I'll start off with 5 into 2 that's
10 10 is already marked 5 into 3 15 15
is already marked 5 into 4 20 20 is
already marked ready is already marked 5
into 5 25 that's where I mark it zero
perfect five is
done what's the next number six for six
do I need to do do I need to do anything
because 6 is not a prime 6 into 2 is
basically 12 that would be marked by
someone who marked six 6 was marked by 2
and three because 2 and three both have
multiples as six so they would have
marked 12 and 6 into 3 18 as well 6 into
4 24 as well so I don't need to do
anything got it perfect let's go to the
next number seven Fine 7 is 1 7 into 2
is
14 so you can go ahead and Mark it 7
into 3 is 21 you can go ahead and Mark
it 7 into 4 is 28 you can go ahead and
Mark it all of them were marked so you
don't do anything and you move
ahead for eight do I need to do no for 9
do I need to do no for 10 do I need to
do no for 11 do I need to do yes because
11 is a prime so 11 into 2 is 22 so you
can go ahead and Mark 22 11 into 3 is
that is beyond the boundary so you stop
perfect for 12 no need for 13 again you
can do and you can keep on doing you can
keep on doing at the end of the day this
is the array that you will be having at
the end of the day this is the array
that you will be having
right if I see what numbers are marked
as one so two is marked as one three is
marked as one five is marked as one 7 is
marked as 1 11 is 13 is 17 is 19ers and
29ers and ready three how is 23 is 23 a
prime yeah it is a prime 23 is also
marked as one so all of these numbers
that are priming till 30 are marked as
one apart from that all the numbers are
marked as zero very simple now I have an
AR I have an AR primes if I ask you hey
if five is a prime so you'll be like
Prime of five equal to equal to 1 yes it
is a prime so I have a black box that
can tell me the answer and be go fun but
what I need to do is some
precomputation some precomputation is
what I need to do now this
pre-computation is known as save of
aosth got
it I I'll write the code then we'll try
optimizing that as well the code is very
simple function which takes n I'll have
to print down all the prime numbers till
in so first of all we can have a primary
of size n + 1 please make sure you run a
fall loop from 2 to n and Mark
everything as one Mark everything as one
so that's very simple you can start off
the loop from Two and you can go on till
n and you can say Prime of I equal to 1
if you're using C++ you can use memet
for Java there might be something like
that you can use it as well so this is
what I'll do initially done what is my
next job my next job is to iate from the
number
two till
n and what do I do I'm saying hey if the
number is prime if it is marked as one
if it is marked as one
then I go over it's multiple and Mark
all the multiples as zero that's what
I'm doing okay so I'm saying okay fine
I'll start a Lo J and that starts from 2
into I and J goes till n because that is
the max I need and will it be
j++ no it won't be j++ it will be j+
equal to i
y if if I take
five 5 into 2 is 10
5 into 3 is 15 so a shift of five
there's a shift of five that is why I'm
doing plus I that is why I'm doing plus
I got it okay fine what do what do I do
I Mark all the multiples as Z that is
the thing that I'm doing if is completed
for Loop is completed I'll not be
calculating the time complexity because
you cannot pinpoint the time complexity
of this one this Loop is easy easy to
compute but this one will be varing
according to the ey so we cannot
pinpoint I try to optimize this is this
the most optimal solution probably not
but you have your Prime ready you have
your Prime array ready so now in order
to print all the prime numbers till n
what you need to do is need to run Loop
till n and you need to say
if Prime of I is equal toal to 1 you
just have to print I so I've trimmed
down trimmed down the square root of n
into B go of one the only thing I need
to do is make sure this pre-computation
is done in the most optimal time
possible so so now I'll try to optimize
this let's try to optimize
this some
observations so the first observation
some so in order to optimize this we'll
have to do some observations let's start
with the first observation it's very
simple we started with the first Prime
two and we marked 2 into two then 2 into
3 then 2 into 4 then 2 into 5 and so on
for the next prime which is three we
started marking 3 into 2 3 into 3 3 into
4 3 into 5 and so on for the next prime
five we started 5 into 2 5 into 3 5 into
4 5 into 5 and so on for the next PL 7
into 2 7 into 3 7 into 4 7 into 5 7 into
6 and 7 into 7 okay tell you one
thing for this two it is absolutely okay
to start with 2 into two but for this
three I'm saying 3 into two I'm saying 3
into two do I need to do it because this
is already been marked over here the St
have already marked three into 2 right
so do I need to start from 3 into 2
doesn't make sense 3 into 3 is the first
number that I start from 9 and then I go
ahead for 12 12 would be marked but that
is okay but if I start from 3 into three
will it work it will let's look it over
here 5 into 2 would already been marked
by 5 into 2 2 into 5 2 into 5 2 into 5
would have already marked 3 into 5 would
have already been marked here 5 into 4
which is 20 and four is a multiple of
two so that have been already been M by
two okay so you actually start from 5
into 5 which is 25 and that's the first
number youa same with 7 7 into 2 would
have been marked by two 3 into
7 by 2 by 5 and by two or three 42 cuz
this is 42 which would be marked by
either two or three agreed so you
actually start from 7 into
7 so what I observe is I don't need to
start from 7 into two like basically I
don't need to start from I into two I
can straight away start from I into I I
can straight away start from I into I
okay perfect I can straight away start
from I into I I know this one
optimization done what is the next
optimization
if I'm starting from I into y let's take
the number
as the number is 30 right n is
30 and the moment I reach 6 the moment I
reach six what happens is I is six okay
and this is
false fine after that I is 7 and this is
2 true what happens to the J Loop is 7
into 7 that's 49 49 lesser than 30 is
false so actually you don't Mark
anything beond you don't mark because 7
into 7 have exceeded your number right
so do I need to go till end I don't need
because you have a condition as I into y
so the max you need to go is till square
root of 30 that's 5 something see if you
go till five it will work if you go till
5 it will look because for five the
inner loop will be 5 into 5 that's 25
and you'll Mark 25 as
zero got it so you don't need to Loop
till this instead of it you can do
square root of n so you can write the
for loop as for I = 2 I into I lesser
than n and I ++ if you write this it
will be absolutely fine so you're
optimizing and we have optimized a lot
so you might be thinking okay we're
doing a lot of pre-computation but what
is the time complexity first of all
we're running a bigo of n Loop in order
to mark all the numbers as one so that's
a bigo of in this one I cannot explain
you because this is something which is
math ma atically proven and the time
complexity is n logarithmic of log of n
that is the time complexity and it's
because it's a prime harmonic
series and no one will be asking you to
derive the time complexity because it is
extremely complicated so do not get into
it just remember that the time
complexity is n log of login it's not
login it's log of login okay and after
that this is another Meo of n so in
order to print all the Primes till n the
time complexity is B of n plus n
logarithmic log of n plus b of n again
this is a pseudo code you find the C++
Java Python and JavaScript code given
below you can check it out and what will
be the space complexity I'm using an
extra space of B go and in order to make
make sure I create that black box got it
so that was it for SE of aats te I hope
that I got that correct so if you
understood everything please please do
consider giving us a like and if you
need to our channel do consider
subscribing to us as well with this I'll
be wrapping up this video Let's Wait in
some other video till then byebye take
care
broken
golden
Voir Plus de Vidéos Connexes
Python Programming Practice: LeetCode #1 -- Two Sum
L3. Longest Substring Without Repeating Characters | 2 Pointers and Sliding Window Playlist
How to Find the LCM (2 Different Ways) | Least Common Multiple | Math with Mr. J
Projeto e Análise de Algoritmos - Aula 10 - Ordenação em tempo linear
Prime numbers | Factors and multiples | Pre-Algebra | Khan Academy
BAB 3 Menentukan Faktor Positif | Matematika Dasar | Alternatifa
5.0 / 5 (0 votes)