首页 文章

SPOJ上的时间超出错误

提问于
浏览 次
-2

彼得想为他的 cryptosystem 生成一些 prime numbers . 帮助他！你的任务是 generate all prime numbers between two given numbers!

Input

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

Output

对于每个测试用例，打印所有素数 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;   
}
c algorithm

2 回答

  • 0

    计算质数的最简单快速方法是使用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 . 查看链接以获取详细信息 .

    来自wikipedia(Sieve of Erastothenes)的SoE算法 .

    回复于
  • 0

    您需要应用sieve of Eratosthenes来解决给定时间限制内的问题 . 检查每个数字是否是逐个素数将太慢 .

    编辑：事实上，筛应该是分段的，而不是完整的eratosthenes筛 .

    回复于

相关问题