Неправильный ответ на SPOJ (PRIME1) - PullRequest
Новая
       63

Неправильный ответ на SPOJ (PRIME1)

0 голосов
/ 10 июля 2019

Вот ссылка на проблему -> PRIME1

Он просит нас напечатать все простые числа между двумя числами m и n

Я использовал сегментированное ситорешить проблему.Сохранял все простые числа до sqrt (10 ^ 9) и использовал их для получения простых чисел в определенном диапазоне.Пожалуйста, помогите мне. 

#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");
    }
}
...