2065. Вася и простые числа

 

Вася на уроке математики узнал, что простыми называются натуральные числа, которые делятся только на 1 и сами на себя, причём число 1 к простым почему-то не относится. А ещё Вася узнал, что некто Петя любит давать много задачек с кодовым названием "от l до r". Вот Вася и придумал себе новую задачку: посчитать количество простых чисел на промежутке от l до r.

 

Вход. Состоит из нескольких тестов. Каждый тест размещён в отдельной строке и содержит два целых (возможно отрицательных) числа l и r (l ≤ r, |l|, |r| < 106). Последняя строка содержит два числа -1 и не обрабатывается.

 

Выход. Для каждого теста вывести в отдельной строке количество простых чисел в диапазоне от l

 

Пример входа 1

Пример выхода 1

4 10

0 5

-1 -1

2

3

 

 

Пример входа 2

Пример выхода 2

10 20

-555 3

-1 -1

4

2

 

 

РЕШЕНИЕ

решето Эратосфена

 

Анализ алгоритма

Запустим решето Эратосфена для чисел до 106. Далее заполним массив cnt так что cnt[i] содержит количество простых чисел, не больших i. Очевидно что cnt[i] = cnt[i – 1] + 1 если i простое и cnt[i] = cnt[i – 1] иначе. Тогда количество простых чисел на промежутке от l до r равно cnt[r] – cnt[l – 1].

Простыми могут быть только натуральные числа. Если l или r не натуральное, то установим его значение равным 1. Тогда например запрос на интервале [-34; 56] эквивалентен запросу на [1; 56], а запрос на [-34; -3] эквивалентен запросу на [1; 1].

 

Реализация алгоритма

Объявим массив primes для решета Эратосфена и массив cnt для подсчета количества простых чисел.

 

#define MAX 1000010

bool primes[MAX];

int cnt[MAX];

 

Решето Эратосфена. Заносим primes[i] = true, если i простое. Иначе положим primes[i] = false.

 

void gen_primes(void)

{

  int i, j;

  for(i = 0; i < MAX; i++) primes[i] = true;

  primes[0] = primes[1] = false;

  for(i = 2; i <= (int)sqrt(1.0*MAX); i++)

    if (primes[i])

      for(j = i * i; j < MAX; j += i) primes[j] = false;

}

 

Основная часть программы. Запускаем решето Эратосфена.

 

gen_primes();

 

Заполним массив cnt так что cnt[i] равно количеству простых чисел, не больших i.

 

memset(cnt,0,sizeof(cnt));

for (i = 2; i < MAX; i++)

  if (primes[i]) cnt[i] = cnt[i-1] + 1; else cnt[i] = cnt[i-1];

 

Читаем запрос – пару l, r.

 

while(scanf("%d %d",&l,&r))

{

  if (l == -1 && r == -1) break;

 

Если l или r не натуральное, то установим его значение равным 1.

 

  if (l <= 0) l = 1;

  if (r <= 0) r = 1;

 

Выводим ответ – количество простых чисел на промежутке от l до r.

 

  printf("%d\n",cnt[r] - cnt[l-1]);

}