Prime Numbers Problem

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

1 Like

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;
}

`

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.

1 Like

Thanks man this is what I was looking for