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上的時間超出錯誤

回答

相關問題