Prime Visits of PMO

#1

https://ide.codingblocks.com/s/168484 it shows the time limit exceeds

#2

Hello Piyush,
You are getting time limit exceeded because your solution time complexity is roughly O(n*max(a,b)*max(a,b)) which is almost order of O(n^3) .
so to make your solution efficient you can use sieve of Eratosthenes and preprocessing.
I hope you will find this helpful.
regards
Aman yadav

#3

i didnt actually get it completely please explain

#4

see what you are doing , you are going from a to b and checking each number whether it is prime or not right. and to check prime you are using another loop right(extra loop).
so I m telling you to use sieve to answer whether a number is prime or not as this will avoid your extra loop.
I hope it is clear now.
suggestions - please once revisie sieve of eratosthenes concept.
regards
Aman yadav

#5

ok so what i got is we remove those numbers between 2 to n which are divisible by any no in between right i am using vectors for it now suppose if i get a element(say 10) which is divisible by( say 5) then i remove remove 10 from using erase now will the indexes of the vector will arrange itself again and how to handle that situation

#6

right you got it correct

#7

but we don’t implement it like that

#8

we simply maintain a boolean array and mark all divisible element as false

#9

bool prime[n+1];
initialise all entry of prime array with true
prime[0]=prime[1]=false;
for (int p=2; p*p<=n; p++)
{

    if (prime[p] == true) 
    { 
        for (int i=p*p; i<=n; i += p) 
            prime[i] = false; 
    } 
}

refer this code snippet, after running this code
if prime[i] is true that means i is prime otherwise not prime
I hope this will make sense to you.if still not clear then please ask
regards
Aman yadav

#10

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

#11

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

#12

can u please dry the above code for n=10 . I think after dry run you will get clear idea of working of sieve.

#13

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

#14

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)

#15

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

#16

@Learning_bunny hey Piyush if your doubt is cleared then please mark it resolved

#17

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

#18

i was gone for some interview thats why i didnt replied

#19

@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.

#20

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.