Prime Numbers Problem

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


This may help you.

1 Like

thanks man :slight_smile:

@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 :slight_smile:

didn’t get that please if you could ad some comments ,it would be more helpful :slight_smile:

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 :slight_smile: