SPOJ의 시간 초과 오류

Question

Peter는 암호 시스템에 대해 prime numbers을 생성하려고합니다. 그를 도와 라! 귀하의 작업은 두 주어진 숫자 사이의 모든 소수를 생성하는 것입니다!

입력

입력 한 줄 (t<=10)에서 테스트 케이스의 수를 t로 시작한다. 다음 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; 
} 

Answer 1

소수를 계산하는 가장 간단한 방법은 Sieve of Erastothenes를 사용하는 것입니다. Segmented Sieve of 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. 

: 알고리즘이다. 자세한 내용은 링크를 확인하십시오.

SoE 알고리즘 wikipedia(Sieve of Erastothenes).

Answer 2

주어진 시간 제약 조건에서 문제를 해결하려면 sieve of Eratosthenes을 적용해야합니다. 각 숫자가 하나씩 소수인지 점검하는 것은 너무 느립니다.

편집 : 실제로 체는 에라토스테네의 전체 체가 아니라 분절되어야합니다.