Задача 349. Простые числа. acmp.ru C++

Масса олимпиадных задач связаны с простыми числами, в частности с их поиском и определением простоты. Поэтому, прежде чем начинать разбор данной задачи, поговорим сначала о том, как определить простоту конкретного числа. Известно, что если число 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
}
}
Для того, чтобы довести вышеописанный алгоритм до алгоритма решения исходной задачи достаточно в процессе поиска проверять добавление нового простого числа на попадение в заданный отрезок и выводить его в случае принадлежности. И не забудьте про двойку!

Если беспокоиться о скорости решета Эратосфена, то
1. Условие выхода из цикла в строке 11 можно перебить на i*i<=N
2. Идти по решету только если первое число простое (поставить условие перед циклом строки 12)
3. Начинать вычёркивать не с j=2*i, а с j=i*i (все числа меньше уже вычеркнуты)
Ну и подумать о быстром заполнении начального массива - на фоне этих ускорений это уже станет важным.

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