Простые числа

Масса олимпиадных задач связаны с простыми числами, в частности с их поиском и определением простоты. Поэтому, прежде чем начинать разбор данной задачи, поговорим сначала о том, как определить простоту конкретного числа. Известно, что если число n составное, то один из его делителей не превосходит значения sqrt(n), поэтому при проверке на делимость числа n достаточно перебрать всевозможные делители от 2 до sqrt(n). Это можно оформить в виде следующей функции:

  bool IsPrime(int n){
    int i;
    for i=2..sqrt(n)
     if(n mod i = 0) return false;
    return true;
  }

Описанную выше функцию можно ускорить вдвое, если проверять делимость только на нечетные числа, а делимость на 2 рассмотреть отдельно. Так же когда уже известны все простые числа, не превосходящие sqrt(n), то еще более разумно проверять делимость только на них, тогда скорость возрастет в ln(sqrt(n)) раз. Следующий фрагмент программы демонстрирует заполнение массива p[i] простыми числами от 2 до n:

  p[1]=2; np=1               //в массив p вносим первое простое число 2 (всего np чисел)
  for x=3..n{                //цикл по нечетным значениям x, которые проверяем на простоту
    j=1; Ok=true;
    while(p[j]*p[j]<=x){     //проверяем число x на делимость на возможные раннее найденые простые числа
      if(x mod p[j] = 0){
        Ok=false; break
      }
      j=j+1
    }
    if(Ok){                  //если делитель не найден, то добавляем данное число в список простых
      np=np+1
      p[np]=x
    }
  } 

Для того, чтобы довести вышеописанный алгоритм до алгоритма решения исходной задачи достаточно в процессе поиска проверять добавление нового простого числа на попадение в заданный отрезок и выводить его в случае принадлежности. И не забудьте про двойку!

[Все попытки] [Задача]