SPOJ PRIME1：TLE [英] SPOJ PRIME1 : TLE

问题描述

我想实现分段筛算法这个[提问]：HTTP：//www.spoj.pl/problems/PRIME1/如下：

I tried implementing the segmented sieve algorithm for this [question]:http://www.spoj.pl/problems/PRIME1/ as follows :

#include <iostream>
#include <string>
#include <set>
#include<math.h>
#include<vector>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cstdio>
#define MAX 32000 // sqrt of the upper range
using namespace std;
int base[MAX];  // 0 indicates prime

vector<int> pv;   // vector of primes

int mod (int a, int b)
{
   if(b < 0)
     return mod(-a, -b);   
   int ret = a % b;
   if(ret < 0)
     ret+=b;
   return ret;
}
void sieve(){

     for(int i = 2 ; i * i < MAX ; i++ )
        if(!base[i])
           for(int j = i * i ; j <  MAX ; j += i )
                 base[j] = 1;

     for(int i = 2 ; i < MAX ; i++ )
         if(!base[i]) pv.push_back(i);

}
int fd_p(int p ,int a ,int b){  // find the first number in the range [a,b] which is divisible by prime p

/*  while(1){

        if(a % p == 0 && a !=p) break;
    a++;
    }
    return a;
*/  

    if(a != p){
        return (a + mod(-a,p)) ;

    }
    else{
     return (a + p);
    }

}
void seg_sieve(int a , int b){

    if(b < 2 ){ 
        cout << "" ;
    return;
    }
    if(a < 2){
      a = 2; 
    }
    int i,j;
    int seg_size  = b - a + 1;
    int*is_prime = new int[seg_size];
    memset(is_prime,0,seg_size*sizeof(int));

    vector<int> :: iterator p ;


    for(p = pv.begin(); p!=pv.end(); p++){
       int x = fd_p(*p,a,b);  

       for(i = x; i <= b; i += *p )
           is_prime[i - a] = 1;
      }

for(i=0; i < b - a + 1; i++)
    if(!is_prime[i])
        printf("%u\n", i + a);

 delete []is_prime ;
}


int main()
{
     sieve();
     int a,b,T;
     scanf("%d",&T);

     while(T--){
     scanf("%d%d",&a,&b);
     seg_sieve(a,b);
     printf("\n");   
     }
//     cout<<endl;
//     system("PAUSE");
     return 0;
}

我收到TLE不过......我不明白什么其他的优化​​将是必需的。 PLZ帮助..

I am getting TLE nevertheless .. I don't understand what other optimization would be required . Plz help ..

编辑1：只是试图实现fd_p（）在固定时间内... [失效] ..嘿，如果ü可以帮助我解决这个错误。

Edit 1 :just tried to implement fd_p() in constant time ... [failure] .. plz if u could help me with this bug..

编辑2：问题已解决

推荐答案

您可以在区间的第一个数字[A，B]这是整除p在固定的时间。尝试做到这一点，我想你应该是好去。

You can get the first number in the interval [a,b] that is divisible by p in constant time. Try to do that and I think you should be good to go.

这篇关于SPOJ PRIME1：TLE的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！