-1

I'm aware this has been asked before, but I cannot fully understand how to implement Segmented Sieve of Eratosthenes.

Problem

The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space. For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.

My approach

I could implement Sieve of Eratosthenes and I can find prime numbers up to square root of n. But I'm not able to understand how to implement the "offset" that is being discussed on other sites. How to perform a Sieve on a selected partition?

#include <stdio.h>
#include <iostream>
#include <math.h>
using namespace std;

int main()
{
    int t;
    cin>>t;

    while(t--)
    {
        long long m,n;
        long long p[100001];
        bool primes[100000];

        cin>>m;
        cin>>n;
        long long square=sqrt(n);
        cout<<square;
        int j=0;
        int i;
        primes[0]=false;    
        primes[1]=false;

        for(i=2; i<n;i++)
            primes[i]=true;

        for(i=2; i<=square; i++)
        {
            if(primes[i]==true)
            {
                for(j=i+i; j<=n; j+=i)
                    primes[j]=false;
            }
        }

        for(i=m; i<n ; i++)
        {
            if(primes[i]==true)
            {
                cout<<i<<" \t";
                if(i >= m)
                {
                    p[j]=i;
                    j++;
                }
            }
        }

        for(i=0 ; i<j ; i++)
        {
            cout<<p[i]<<"\n";
        }
    }

    return 0;
}
Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
user3125772
  • 73
  • 1
  • 10

2 Answers2

1

Consider a segment S : [a,b] and a prime p.

Note that the following code will eliminate all composites "corresponding" to prime p.

for(int i=ceil(a/p);i<=floor(b/p);++i) {
    new_primes[i*p-a]=false;

Extend this idea for all primes <= sqrt(b).

donkey
  • 463
  • 1
  • 4
  • 14
0

First of all since you mentioned you are coding for SPOJ, I'll tell you that this is not going t work. Even if you somehow got a method to do SOE just from m to n, you would be performing such seives t times, which is going to give you TLE.

What is excpected is a simple precompute of SOE through the entire range, i.e. from 1 to 10^x. First outside your while loop perform SOE and store all primes into a vector. Then in your while loop simply display the required primes from the vector.

Kartik_Koro
  • 1,277
  • 1
  • 11
  • 23
  • I used a boolean array _primes_ for sieving and a vector _prime_ to store/precompute the primes'for(i=m; i<=n ; i++) { if(primes[i]==true) { prime.push_back(i); //cout<=m && prime[i]<=n) cout<n) break; } //' **I tried this but it didn't work. How to actually implement this? (It works for upto 10^5 and it doesn't work for larger values of m and n)** – user3125772 May 30 '14 at 13:44
  • Pushback all primes into your vector outside the while loop. Inside your while loop simply go through your vector till you find prime>m and print till you find prime >n . Probably it's only working till 10^5 for you because you are using int somewhere, Use long long int everywhere you should be fine. One thing to note is sometimes your computer's compiler won't allow you to create a bool array of size 1000000000 for the sieve, but spoj will allow you, I've done it before, I tested on ideone as well just now, creation of such large arrays is allowed. http://ideone.com/qX2LNP – Kartik_Koro May 30 '14 at 14:03
  • I got a run-time error. Not working for big numbers...http://ideone.com/cAhNWh – user3125772 May 30 '14 at 14:32