SPOJ PRIME1：TLE

Question

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

#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帮助..

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

编辑2：解决的问题。

Answer 1

您可以得到在恒定时间内可被p整除的区间[a，b]中的第一个数字。试着这样做，我认为你应该很好去。

Answer 2

很多年前我已经解决了这个问题。假设，该n-m < = 100000 您需要计算1和sqrt之间的所有Primes（1000000000）< 40000. 比手动测试n和m之间的每个数字。这将是多余的

program prime1; 
    Var 
    t:longint; 
    m,n:longint; 
    i,j,k:longint; 
    prime:array of longint; 
    bool:boolean; 
begin 
SetLength(prime,1); 
prime[0]:=2; 
for i:=3 to 40000 
    do begin 
    j:=0; bool:=true; 
    while (prime[j]*prime[j]<= i) do begin 
    if (i mod prime[j] = 0) then begin 
     bool:=false; 
     break; 
    end; 
    inc(j); 
    end; 
    if (bool) then begin 
    SetLength(prime,length(prime)+1); 
    prime[length(prime)-1]:=i; 
    end; 
end; 
readln(t); 
for k:=1 to t do begin 
    readln(m,n); 
    for i:=m to n do begin 
    if (i=1) then continue; 
    j:=0; bool:=true; 
    while (prime[j]*prime[j]<= i) do begin 
    if (i mod prime[j] = 0) then begin 
     bool:=false; 
     break; 
    end; 
    inc(j); 
    end; 
    if (bool) then 
    writeln(i); 
    end; 
    writeln; 
end; 
end. 

Answer 3

您已经完成了最后一步的改进。 只适用于赔率。

我们知道2是素数，我们知道甚至没有偶数（2除外）是素数。所以没有必要检查它们。

埃拉托塞尼的筛子为奇素数是P = {3,5，...} \ Ú {{^{p 2}，^{p 2 +} 2P，... } | p in P}。实施这将足以让你通过：

• 特别处理2作为一个单独的案件。使用正常大小的一半数组，其中在偏移量i处的数组条目表示奇数值ao + 2*i，其中ao = a|1是不低于a的最小奇数。这意味着增量值2p对应于数组中偏移量的增量p。
• 偏移筛列中的素数p等于或大于p*p的起始奇数倍数为m = p*p >= ao ? p*p : ((ao+p-1)/p)*p; m = m&1 ? m : m+p;，条件是p <= sqrt_b。筛网阵列中的相应偏移量为(m-ao)/2。

作为一个便笺，你的命名很混乱：is_prime实际上是is_composite。

Answer 4

问题是你的fd_p函数太慢了，增加a直到你找到一个很好的值来开始你的筛选，那么肯定会超时，因为a可能在10亿的范围内。

虽然你有正确的想法。

看到这个博客帖子有工作代码，以及一个更容易理解的解释：

http://www.swageroo.com/wordpress/spoj-problem-2-prime-generator-prime1/