we are initializing the array which has numbers till n from 1 or 2 mean arr[0] is 1 or 2 and why had we initialized prime[0]=prime[1]=false
Prime Visits of PMO
we are initialising prime[0]=false and prime[1] equal false becuase 0 and 1 are not prime numbers.
In general after applying sieve ,for any index i >=0 && i<=n if prime[i]=true that means i is a prime number else it is not prime
can u please dry the above code for n=10 . I think after dry run you will get clear idea of working of sieve.
get it now but one thing that here we have are given a range like 11 to 20 or some other range…now do we have to cahnge our code like size of boolean array or range of i
great i am glad finally you got this.
Now to answer range query first you need to maintain an array whose entry at ith index will tell you number of prime from 0 to i.
Now if you are given to tell number of prime between a to b then you can simply
return arr[b]-arr[a-1] ( number of primes from 0 to b minus number of prime from 0 to a-1)
consider an example
lets n=10
then sieve array will look like (here value 0 means false and value 1 means true)
index - 0 1 2 3 4 5 6 7 8 9 10
value - 0 0 1 1 0 1 0 1 0 0 0
now using this sieve array maintain another array let say arr (its ith entry will tell u number of primes from o to i)
so for given sieve arr array will look like
index - 0 1 2 3 4 5 6 7 8 9 10
value - 0 0 1 2 2 3 3 4 4 4 4
here arr[3] means number of prime between o to 3 which is 2 { 2,3}
arr[5] means number of prime between o to 5 which is 3 { 2,3,5}
now let say you are asked to tell prime numbers between a=3 to b=8
answer will be to find all prime numbers between 0 to 8 and then subtract all prime numbers between 0 to 2
ie arr[8]-arr[2] = 4- 1=3
so 3 prime numbers are there in between 3 to 8 i.e {3,5,7}
I hope with this example you will get a better clarity.
suggestions - please take some example on your own and try to find answer manually
if i use vector instead of array and first inserts all number from 3 to n which are not divisible by 2 as factors of 2 are not prime then inserts 2 in beginning of it and then use sieve on the vector using a for loop remove elements from 0 to a then print the remaining vector is this a good approach
i was gone for some interview thats why i didnt replied
@Learning_bunny no this is not good approach.the best way is what i said above and it time complexity is roughly O(nlog(log(n))). also don’t worry about sieve implementation. the code snippet i shared above is standard way of implementing sieve and everyone do it in that way only.so use that snippet whenever u need sieve without any hesitation.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.
i am not able to see that code snippet will you please send it again
@Learning_bunny
here is the link - Prime Visits of PMO
please tag using this symbol @ otherwise it will not give notification to me
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.
https://ide.codingblocks.com/s/168484 values for 1 to 10 are not right when i trying to get prime from 1 to 10 it is showing 1,5,7
@Learning_bunny Since you are trying this question since 23 days I would like to give you the soultion.