2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Псевдопростые числа
Сообщение26.04.2014, 12:13 


10/05/13
251
Задача формируется так:
Будем называть число Псевдопростым для некого натурального числа $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;
   }

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

 Профиль  
                  
 
 Re: Псевдопростые числа
Сообщение06.05.2014, 00:43 
Заслуженный участник
Аватара пользователя


28/07/09
1178
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$.

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

 Профиль  
                  
 
 Re: Псевдопростые числа
Сообщение06.05.2014, 08:27 
Заслуженный участник


20/12/10
8858
frankenstein в сообщении #855203 писал(а):
Будем называть число Псевдопростым для некого натурального числа $k$, если оно не делится на натуральные числа
на отрезке $[ 2, ..., 2+k-1 ]$
Нехорошо использовать уже занятый термин "псевдопростое число". Тем более что в данном случае условие "не делится на натуральные числа на отрезке $[ 2, ..., 2+k-1 ]$" равносильно условию "взаимно просто с $(k-1)!$".
Legioner93 в сообщении #859614 писал(а):
Если заинтересуетесь моей формулой, то с удовольствием расскажу, как получил.
Поясните, я ничего не понял в коде программы. Вряд ли есть простая аналитическая формула для количества тех чисел, которые определил ТС. Всё-таки в задаче присутствуют три независимых параметра $a$, $l$, $k$.

 Профиль  
                  
 
 Re: Псевдопростые числа
Сообщение06.05.2014, 11:24 
Заслуженный участник
Аватара пользователя


28/07/09
1178
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}$$

 Профиль  
                  
 
 Re: Псевдопростые числа
Сообщение06.05.2014, 11:33 
Заслуженный участник


20/12/10
8858
Legioner93 в сообщении #859755 писал(а):
Определяет количество чисел на $[x,y]$, кратных $d$
А, вот Вы о чём. Ну, это-то понятное дело. Мне показалось, Вы пишите о формуле, которая бы давала ответ на задачу ТС:
frankenstein в сообщении #855203 писал(а):
Задача такая, даны натуральные числа $a, l, k$.
Требуется посчитать количество Псевдопростых для $k$ чисел на отрезке $[a+1, a+2, ..., a+l]$

 Профиль  
                  
 
 Re: Псевдопростые числа
Сообщение14.05.2014, 09:04 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Псевдопростые числа
Сообщение18.05.2014, 10:28 


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

 Профиль  
                  
 
 Re: Псевдопростые числа
Сообщение18.05.2014, 11:37 


10/05/13
251
Да, вы правы, ведь можно решить системой непересекающихся множеств.
Обозначим через $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] )
...
$ :| Дальше затрудняюсь... :-(

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group