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

    Тук ще разгледам алгоритъм за намиране на прости числа във зададен интервал. Това е модификация на алгоритъма на Ератостен, като може да се каже че е един от най-добрите алгоритми.
     Нека първо разгледаме алгоритъма на Ератостен в най общи линии. През 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;
}
Източник: http://www.eadvise.info