How to solve this Problem ? Any solution in C++ will be more helpful . Thanks in advance

This may help you.

thanks man

@gagan86nagpal could you provide itâ€™s cpp implementation â€¦ I am having problem in implementing it .

using namespace std; int a[3125005]; void precomp() { for(int i=0;i<3125000;i++) a[i]=0; a[0]|=(1<<1); for(int i=2;i<=1768;i++){ for(int j=i*2;j<=1768;j+=i){ a[j/32]|=(1<<(j%32)); } } } int main() { precomp(); int t; scanf("%d",&t); while(t--) { int n,m; scanf("%d%d",&n,&m); for(int i=n;i<=m;i++){ if(((a[i/32]) & (1<<(i%32)))==0) printf("%d\n",i); } } return 0; } ```

didnâ€™t get that please if you could ad some comments ,it would be more helpful

didnâ€™t get that please if you could ad some comments ,it would be more helpful

It is a standard question of segmented sieve. Just google out the geeksforgeeks explanation of it- and check out otherâ€™s code for implementation. Better than waiting for someone to give links.

I am unable to understand the latter part of the code â€¦ what my approach is to form a sieve and then check for the numbers in the range [m-n+1] and filling the sieve again for them from 2 to sqrt(m)[All prime numbers ] and the left out is the answer but implementation is the real problem â€¦@vijju123 . Could you provide a working solution to this problem ? It would be great help . Thanks

You can have a look at my code- https://www.codechef.com/viewsolution/15437598

Yes, the concept says that you find all primes from [1,\sqrt{R}] where R is the upper limit. Then in the range [L,R], you mark out all the multiples of these primes as â€śNot Prime.â€ť The leftover numbers are prime.

In case you are confused on why it works, then the answer is that- to get all prime factors of a number, checking the prime factors from [2,\sqrt{N}] is sufficient, as if there isnt any prime factor \le \sqrt{N}, then there cannot be any factor \ge \sqrt{N} as well.

Thanks man this is what I was looking for