Намиране на простите числа в интервал

Тук ще разгледам алгоритъм за намиране на прости числа във зададен интервал. Това е модификация на алгоритъма на Ератостен, като може да се каже че е един от най-добрите алгоритми.
Нека първо разгледаме алгоритъма на Ератостен в най общи линии. През 275-195г. пр. н.е. Ератостен от Сирен се досетил че простите числа могат да се пресмятат, като:
1. Записваме числата от 2 до n последователно
2. Намираме първото незачертано и немаркирано число - това е 2, маркираме го, след което зачертаваме всяко второ число след него.
3.Аналогично преминаваме на 3 и зачертаваме всяко трето число, като маркираме 3
Така всички маркирани числа са прости. Алгоритъмът е с въвеждане на масив с нули, в който поставяме всички числа, и поставяме знак само на позициите с прости числа.
Модификацията, която предлагам, е с масив, в който се записват само простите числа, а не всички числа в интервала. Вместо да проверяваме числата от 2 до n, можем да разделим този интервал на подинтервали и да проверим за всеки от тях, съдържа ли прости числа. Т.е. след записване на първото просто число(2), ще проверим в интервала [3, 2.2] - това е 3. Следващият интервал ще е [4, 3.3] - 5 и 7 са простите числа там. Реализацията на алгоритъма е на езика С, но вие можете да я модифицирате лесно за всеки друг език.

#include <stdio.h>
#define MAXN 10000
/* намира простите числа до n */
const unsigned n = 500;

unsigned primes[MAXN], pN = 0;

char isPrime(unsigned n)
{
unsigned i = 0;
while (i < pN && primes[i] * primes[i] <= n)
{
if (n % primes[i] == 0)
return 0;
i++;
}
return 1;
}

void findPrimes(unsigned n)
{
unsigned i = 2;
while (i < n)
{
if (isPrime(i))
{
primes[pN] = i;
pN ++;
printf("%5u", i);
}
i++;
}
}

int main(void)
{
findPrimes(n);
printf("n");
return 0;
}