You are not logged in. Please login at www.codechef.com to post your questions!

×

Prime Numbers Problem

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

asked 08 Nov '17, 09:01

harrypotter0's gravatar image

4★harrypotter0
318110
accept rate: 1%

edited 08 Nov '17, 09:02


link

answered 08 Nov '17, 11:16

gagan86nagpal's gravatar image

5★gagan86nagpal
11116
accept rate: 11%

thanks man :)

(08 Nov '17, 11:54) harrypotter04★

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

(08 Nov '17, 12:05) harrypotter04★
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;
}
link

answered 08 Nov '17, 12:29

ramini's gravatar image

2★ramini
615
accept rate: 8%

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

(08 Nov '17, 12:54) harrypotter04★

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

(08 Nov '17, 12:55) harrypotter04★

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) vijju123 ♦♦4★

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) harrypotter04★
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) vijju123 ♦♦4★

Thanks man this is what I was looking for :)

(08 Nov '17, 15:06) harrypotter04★
showing 5 of 6 show all
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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