c++ - SPOJ PRIME1 : TLE-6ren

c++ - SPOJ PRIME1 : TLE

转载作者：塔克拉玛干更新时间：2023-11-03 04:02:22

30

4

<分区>

我尝试为这个[问题]实现分段筛算法: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。我不明白还需要什么其他优化。请帮助..

编辑 1:只是试图在恒定时间内实现 fd_p() ... [失败] .. 如果你能帮助我解决这个错误......请问......

编辑 2:问题已解决。

30

4

0

文章推荐： performance - 从头开始合并列表列表

文章推荐： java - JWT认证: How to implement logout?

文章推荐： java - ModelMapper:确保方法具有零参数并且不返回 void

文章推荐： Javascript 将链接的键值分组到数组中

c++ - 为什么我的 SPOJ GCD2 代码在 SPOJ 上出错？
以下是 SPOJ GCD2 的代码.它在我的机器和 Ideone 上运行良好，但在 SPOJ 上出现运行时错误 (SIGFPE)。我已经检查了 spojtoolkit.com 上也提供的所有测试用例。
algorithm - SPOJ PALIN 程序在 ideone 上成功运行，但在 SPOJ 上发布时显示错误答案
如果正整数在从左到右和从右到左读取时在十进制系统中的表示相同，则称为回文。给定一个不超过1000000位的正整数K，写出大于K的最小回文的值输出。显示的数字始终不带前导零。输入第一行包含整数 t，
c++ - 解决 SPOJ www.spoj.com/problems/PRHYME/的正确方法是什么？
我一直在努力解决这个问题 SPOJ www.spoj.com/problems/PRHYME/?几天了，但没有成功。这是问题的简要说明: Given is a wordlist L, and a
java - NZEC 素数生成 SPOJ- http ://www. spoj.com/problems/PRIME1/
我是编码初学者。我在向 spoj 提交质数生成代码时收到 NZEC 错误。但代码在我的桌面上运行得很好。请帮助我。这就是我编写的代码。 import java.util.*; import java.
c - SPOJ 显示我对 : http://www. spoj.com/BSCPROG/problems/SMPCPH1/的解决方案的错误答案
#include #include #include main() { int n, m, i, j, k; char a[100], b[100]; scanf("%d
c++ - 法丽达公主 on Spoj
我遇到了一个问题 SPOJ . 我检查了所有通过所有测试用例，但我仍然在 spoj 上得到“WA”。我知道它可以使用动态编程来解决，但我正在练习内存。这是我的代码: #include #inclu
c++ - 主教给出错误答案(spoj)
很难说出这里问的是什么。这个问题是含糊的、模糊的、不完整的、过于宽泛的或修辞性的，无法以目前的形式得到合理的回答。如需帮助澄清此问题以便重新打开它，visit the help center 。已关
c - 素数生成器(spoj)
有关确切的问题，请参阅此 link 这里我定义了三个函数，将它们相互调用。函数调用尚未完成 #include int primegen(int x1,int x2); int isprime(int
c - SPOJ 上出现超时错误
Peter 想生成一些 prime numbers对于他的密码系统。帮助他!您的任务是生成两个给定数字之间的所有素数! 输入输入以单行中测试用例的数量t开始(t int main() {
c - SPOJ - 小阶乘
http://www.spoj.com/problems/FCTRL2/ 我的代码在 Spoj 中显示编译错误，尽管在我的编译器中运行准确。 **IDE - 代码块 ** int cal(int );
java - SPOJ 上的小阶乘
我正在尝试将我的代码提交给 SPOJ 上的“小阶乘”问题。它在我的 IDE 上成功运行，但在 SPOJ 上显示运行时错误 (NZEC)。请提出解决方案。 import java.util.Scanne
java - spoj 下一个回文中的时间限制超出错误
我正在尝试解决 SPOJ 中的下一个回文问题。我在下面的 Java 代码中收到超出时间限制的错误。 “如果一个正整数在十进制中从左到右和从右到左读的表示相同，则称为回文。对于给定不超过 1000000
c++ - spoj(歧义排列)
我在 spoj 上解决了一个名为 Ambiguous Permutations(http://www.spoj.com/problems/PERMUT2/)的简单问题，当我测试小输入时它工作正常，但在
c++ - SPOJ 错误答案
我正在尝试关于 SPOJ 的问题，其中我们必须简单地找到 Longest Increasing Sub-sequence 的长度给定数组 A. 我使用动态规划 O(n^2) 算法解决了这个问题，解决方
c++ - SPOJ 字母代码
关闭。这个问题需要更多focused .它目前不接受答案。想改进这个问题吗？更新问题，使其只关注一个问题 editing this post . 关闭 3 年前。 Improve this qu
c++ - SPOJ 中的运行时错误
我刚开始接触竞争性编程。我有点坚持这个素数。 SPOJ 上的生成器问题。代码在 GeeksforGeeks IDE 上运行良好，但在 SPOJ 上它会出现运行时错误。问题是这样的: Peter 想为他
c - Spoj - 混合物
好吧，这让我发疯了。我在 spoj 上解决了一个名为 MIXTURES ( http://www.spoj.com/problems/MIXTURES/) 的问题。我不知道为什么我总是遇到段错误。该问
c - 下一个回文 SPOJ
我已经为下一个回文问题编写了一个蛮力解决方案，并希望获得 Time Limit Exceeded 。但是当我测试了一些测试用例时它工作正常但是当我在 spoj 中提交代码时我得到了错误的答案。这是我的
algorithm - SPOJ 对此解决方案给出了错误的答案
我正在尝试解决 NGON问题。我在这里使用自下而上的动态编程。递归函数为: f(a,b) = f(a-1,b) + f(a-1,b-1)*ai +f(a-1,b-2)*ai*(ai-1)/2, a>0
c++ - Spoj- 数组的最大子集
我正在解决这个 spoj 问题。 http://www.spoj.com/problems/MAXSUB/我所有的测试用例都正常工作，但我在 spoj 中得到了错误的答案。我试图改变我的代码很多但仍然

首页

博学

6Ren·AI

商城

c++ - SPOJ PRIME1 : TLE