SPOJ上的时间超出错误

-2

Peter想为他的密码系统生成一些prime numbers密码系统。帮助他！您的任务是生成两个给定数字之间的所有素数！SPOJ上的时间超出错误

输入

输入开始的测试用例在单行(t<=10)数吨。在下一个t行中，有两个数字m and n (1 <= m <= n <= 1000000000, n-m<=100000)由空格分隔。

输出

对于每个测试实例打印所有素数p使得m <= p <= n，每行一个数，测试用例由空行分隔。

这里是链接http://www.spoj.com/problems/PRIME1/

我想出了这个解决方案，但它显示的时间超过了错误，所以我怎么能提高呢？

#include<stdio.h> 
int main() 
    { 
     int n,a,i,b; 
     scanf("%d",&i); 
     while(i>0){ 
     scanf("%d",&a); 
     scanf("%d",&b); 
     while(a<=b){  
      for(n=2;n<=a;n++){ 
      if(a%n==0)break; 
      } 
      if(a==n){ 
      printf("%d\n",a); 
      } 
     a++; 
     } 
    i--; 
    printf("\n"); 
} 
return 0; 
}

来源

2014-07-11 KapilSantore

链接到一个活的网站是没有用的未来在这个问题上的兴趣..请添加一个小提琴.. –

@JF it; “链接到现场网站”？ – KapilSantore

计算质数的最简单快速方法是使用Erastothenes筛。该算法是：

1)Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n). 
2)Initially, let p equal 2, the first prime number. 
3)Starting from p, enumerate its multiples by counting to n in increments of p, and mark them in the list (these will be 2p, 3p, 4p, etc.; the p itself should not be marked). 
4)Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this new number (which is the next prime), and repeat from step 3.

对于此问题，您将需要使用Segmented Sieve of Erastothenes。详细信息请查看链接。

SoE Algorithm from wikipedia(Sieve of Erastothenes)。

来源

2014-07-11 12:55:30

@KarolyHorvath这就是为什么我说使用分段筛.... –

您需要申请sieve of Eratosthenes来解决在给定的时间限制内的问题。检查每个数字是否是一个一个素数会太慢。

编辑：实际上筛应该分割，而不是一个完整的eratosthenes筛。

来源

2014-07-11 12:46:46

“m <= n <= 1000000000，n-m <= 100000” - 这是错误的方法。 –

@KolyolyHorvath不仅是它不是一个错误的方法，但我也解决了这个方法的同样的问题。也许我需要提到应该使用[分段筛]（http://stackoverflow.com/q/10249378/812912）。 –

SPOJ上的时间超出错误

回答

相关问题