c - SPOJ 上出现超时错误

Question

Peter 想生成一些 prime numbers对于他的密码系统。帮助他!您的任务是生成两个给定数字之间的所有素数!

输入

输入以单行中测试用例的数量t开始(t<=10) 。接下来的每一行都有两个数字 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;   
}

Answer 1

计算素数的最简单快速方法是使用埃拉斯托尼筛法。该算法是:

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 算法来自wikipedia(Sieve of Erastothenes) .