Псевдопростые числа

[frankenstein]

Задача формируется так:
Будем называть число Псевдопростым для некого натурального числа $k$, если оно не делится на натуральные числа
на отрезке $[ 2, ..., 2+k-1 ]$
Задача такая, даны натуральные числа $a, l, k$.
Требуется посчитать количество Псевдопростых для $k$ чисел на отрезке $[a+1, a+2, ..., a+l]$

Я решил решать эту задачу так:
Вот алгоритм который позволяет определить количество делимых на $divisor$ чисел на отрезке $[a+1, ... a+l]$

int divNum(int a, int l, int divisor)
{
   int i = 1;
   // find first divisor in set
   while ((a+i) % divisor)
   {
      if (++i > l)
         return 0;
   }

   return (l-i+1)/divisor + 1;
}

Дальше, чтобы определить количество Псевдослучайных чисел на отрезке $[a+1, ..., a+l]$
Я решил сделать так:

   d = 2;
   S = l;
   while (k--) {
      S -= divNum(a, l, d);
      
      while (!isPrime(++d));
      if (d-1 > k)
         break;
   }

Но алгоритм два раза учитывает некие числа, в результате получается неправильный ответ

[Legioner93]

frankenstein в сообщении #855203 писал(а):

Вот алгоритм который позволяет определить количество делимых на $divisor$ чисел на отрезке $[a+1, ... a+l]$
Код:
int divNum(int a, int l, int divisor)
{
int i = 1;
// find first divisor in set
while ((a+i) % divisor)
{
if (++i > l)
return 0;
}
return (l-i+1)/divisor + 1;
}

Даже если бы в вашей функции не было ошибки (она есть, см. далее), хочу посоветовать...
Не нужно решать совсем «в лоб» такие чисто алгоритмические задачи. 5 минут посидите в следующий раз с бумагой и карандашом, прежде чем бросаться писать натуральный брутфорc.
И вуаля - время выполнения функции из $O(a)$ становится $O(1)$

Вот мой вариант функции

int divNum_true(int x, int y, int d)
{
    return y/d-x/d + !(x%d);
}

В ваших обозначениях это интервал $[(x-1)+1, (x-1)+(y-x+1)]$, то бишь $a=x-1$ и $l=y-x+1$

Собственно, корректность своей формулы не проверял и не доказывал (на глаз верная, но чёрт его знает), ведь главное - сверить её с вашей.
Уже для $[2, 3]$ и $d=2$ моя даёт правильное число делимых $1$ тогда как ваша выводит $2$.

Если заинтересуетесь моей формулой, то с удовольствием расскажу, как получил. Но там всё очень тривиально.

[nnosipov]

frankenstein в сообщении #855203 писал(а):

Будем называть число Псевдопростым для некого натурального числа $k$, если оно не делится на натуральные числа
на отрезке $[ 2, ..., 2+k-1 ]$

Нехорошо использовать уже занятый термин "псевдопростое число". Тем более что в данном случае условие "не делится на натуральные числа на отрезке $[ 2, ..., 2+k-1 ]$" равносильно условию "взаимно просто с $(k-1)!$".

Legioner93 в сообщении #859614 писал(а):

Если заинтересуетесь моей формулой, то с удовольствием расскажу, как получил.

Поясните, я ничего не понял в коде программы. Вряд ли есть простая аналитическая формула для количества тех чисел, которые определил ТС. Всё-таки в задаче присутствуют три независимых параметра $a$, $l$, $k$.

[Legioner93]

nnosipov
Я не находил те числа, которые в итоге ищет ТС. Я вообще не смотрел во вторую часть программы. Для его функции int divNum(int a, int l, int divisor) очевидно есть «простая аналитическая формула», а он ищет первый делитель подбором.

Legioner93 в сообщении #859614 писал(а):

И вуаля - время выполнения функции из $O(a)$ становится $O(1)$

Только, естественно, не $O(a)$, а $O(d)$, ошибся. При $a=l=divisor=1000$ цикл while будет исполняться 1000 раз. Вот, посмотрите его код:

Используется синтаксис C

int divNum(int a, int l, int divisor)
{
   int i = 1;
   // find first divisor in set
   while ((a+i) % divisor)
   {
      if (++i > l)
         return 0;
   }

   return (l-i+1)/divisor + 1;
}

Между тем, «простая аналитическая формула» для количества чисел, кратных $d$ на отрезке $[x,y]$ есть, её я и представил, предлагая заменить ей функцию ТС-а int divNum(int a, int l, int divisor)

Используется синтаксис C

int divNum_true(int x, int y, int d)
{
    return y/d-x/d + !(x%d);
}

Определяет количество чисел на $[x,y]$, кратных $d$
Вот вам то же самое, только математически:

$$ divNum=\begin{cases} \left\lfloor \dfrac{y}{d}\right\rfloor-\left\lfloor \dfrac{x}{d}\right\rfloor,&\text{если $x \not\equiv 0 \pmod d$;}\\ \\ \left\lfloor \dfrac{y}{d}\right\rfloor-\left\lfloor \dfrac{x}{d}\right\rfloor + 1,&\text{если $x \equiv 0 \pmod d$.}\\ \end{cases}$$

[nnosipov]

Legioner93 в сообщении #859755 писал(а):

Определяет количество чисел на $[x,y]$, кратных $d$

А, вот Вы о чём. Ну, это-то понятное дело. Мне показалось, Вы пишите о формуле, которая бы давала ответ на задачу ТС:

frankenstein в сообщении #855203 писал(а):

Задача такая, даны натуральные числа $a, l, k$.
Требуется посчитать количество Псевдопростых для $k$ чисел на отрезке $[a+1, a+2, ..., a+l]$

[Null]

frankenstein, укажите ограничения на $a, l, k$. А то при маленьком $k$ задача решается по формуле включений-исключений за $2^{\pi(k+1)}$, А при маленьком $l\sqrt{a+l}$ или $lk$ можно в лоб перебрать все $l$ чисел.

[frankenstein]

Лучше взгляните на саму задачу в оригинале:
http://acm.timus.ru/problem.aspx?space=1&num=1940

[frankenstein]

Да, вы правы, ведь можно решить системой непересекающихся множеств.
Обозначим через $M_n$
Множество целых чисел на $ [a+1, a+l-1] $ которые делятся на $n$

Решение задачи в данном случае это число
равное количеству чисел на $[a+1, a+l]$, которые не делятся на
целые числа числа из отрезка$[2, k+1]$

Тогда решением задачи будет:
$ l - ( |M_2| + |M_3| + ... |M_{k+1}|) + ( |M_{i}| \cup |M_{j}| : i \ne j; i, j \in [2, k+1] ) ... $ Дальше затрудняюсь...