Prime Numbers Problem

general
,
1

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

2


This may help you.

1 Like
3

thanks man :slight_smile:

4

@gagan86nagpal could you provide it’s cpp implementation … I am having problem in implementing it .

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

```
6

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

7

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

8

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.

9

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

10

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
11

Thanks man this is what I was looking for :slight_smile: