0

Here is the link to the problem -> PRIME1

It asks us to print all the prime numbers between two numbers m and n

I used segmented sieve to solve the problem. Stored all the primes till sqrt(10^9) and used them to get primes in a specific range. Please help me out.

#include <iostream>
#include <vector>
using namespace std;

vector<int> v;
vector<bool> prime(32022);
void precompute()
{
    int n=32000;
    prime[0]=prime[1]=true;
    for(int i=2;i*i<=32000;i++)
    {
        for(int j=i*i;j<=32000;j+=i)
            prime[j]=true;
    }
    for(int i=0;i<=32000;i++)
        if(!prime[i]) v.push_back(i);
}

int main() {
    precompute();
    int t; scanf("%d",&t);
    while(t--)
    {
        int m,n; scanf("%d%d",&m,&n);
        if(n<=32000)
        {
            for(int i:v)
            {
                if(i>n) break;
                if(i>=m && i<=n)
                    printf("%d\n",i);
            }
        }
        else
        {
            vector<bool> prime(n-m+1,true);
            for(int i:v)
            {
                int st=(m/i)*i;
                if(st<m) st+=i;
                while(st<=n)
                {
                    prime[st-m]=false;
                    st+=i;
                }
            }
            for(int i=0;i<n-m+1;i++)
            {
                if(prime[i]) printf("%d\n",i+m);
            }
        }
        printf("\n");
    }
}
Sri Harsha
  • 1
  • 1
  • Offtopic: About [`using namespace std`](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice)... – Aconcagua Jul 10 '19 at 17:00
  • `if(n<=32000)` – with `n` once having passed 32000, you won't ever enter the if branch again. So you might be appending new primes, but you won't check them ever again; you need to increase the count of numbers you have checked already... – Aconcagua Jul 10 '19 at 17:22
  • Having fixed the issue, your algorithm will remain inefficient, you'll be re-checking the primes you already *have* checked, as you constantly iterate over the whole vector. So remember the index of highest prime already checked and re-start there when entering the if-branch again. – Aconcagua Jul 10 '19 at 17:25
  • Concerning efficiency: you perform the Sieve with all steps `i`. Instead, you can use the prime numbers already found only. – Damien Jul 10 '19 at 20:16

0 Answers0