How to solve this Problem ? Any solution in C++ will be more helpful . Thanks in advance asked 08 Nov '17, 09:01

https://www.youtube.com/watch?v=Xxu95iiVcPI This may help you. answered 08 Nov '17, 11:16
thanks man :)
(08 Nov '17, 11:54)
@gagan86nagpal could you provide it's cpp implementation .... I am having problem in implementing it .
(08 Nov '17, 12:05)

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;
}
answered 08 Nov '17, 12:29
didn't get that please if you could ad some comments ,it would be more helpful :)
(08 Nov '17, 12:54)
didn't get that please if you could ad some comments ,it would be more helpful :)
(08 Nov '17, 12:55)
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.
(08 Nov '17, 13:44)
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 [mn+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
(08 Nov '17, 13:58)
1
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.
(08 Nov '17, 14:19)
Thanks man this is what I was looking for :)
(08 Nov '17, 15:06)
showing 5 of 6
show all
