Ошибка превышения времени на SPOJ

Питер хочет генерировать некоторые prime numbers для своей криптосистемы. Помоги ему! Ваша задача - сгенерировать все простые числа между двумя заданными числами!

вход

Вход начинается с числа t тестовых случаев в одной строке (t<=10). В каждой из следующих t строк есть два числа m and n (1 <= m <=n <=1000000000, nm<=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; 
}
</stdio.h>
2 ответа

Самый простой способ вычисления простых чисел - использовать Сито Эрастотенов. Алгоритм:

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.

Для этой проблемы вам нужно будет использовать Сегментированное сито из Erastothenes. Проверьте ссылку для получения дополнительной информации.

SoE Алгоритм из Википедии (Сито Эрастотена).


Вам необходимо применить сито Эратосфена для решения проблемы в заданных временных ограничениях. Проверка того, будет ли каждый номер простым по одному, будет слишком медленным.

EDIT: на самом деле сито должно быть сегментировано, а не полное сито эратосфенов.

licensed under cc by-sa 3.0 with attribution.