×

Prime Numbers Problem

 0 How to solve this Problem ? Any solution in C++ will be more helpful . Thanks in advance asked 08 Nov '17, 09:01 318●1●10 accept rate: 1%

 1 https://www.youtube.com/watch?v=Xxu95iiVcPI This may help you. answered 08 Nov '17, 11:16 111●1●6 accept rate: 11% 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)
 0 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 2★ramini 61●5 accept rate: 8% 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 [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 (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
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,321
×197

question asked: 08 Nov '17, 09:01

question was seen: 270 times

last updated: 08 Nov '17, 15:41