Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 3 из 4 |
[ Сообщений: 32 ] | На страницу Пред. 1, 2, 3, 4 След. |
|
Автор | Сообщение | |
---|---|---|
vorvalm |
|
|
s_e_r_g писал(а): У этих обоих алгоритмов есть несколько общих недостатков Во-первых, они обе не резиновые Во-вторых, для проверки очень больших чисел и та, и другая не годятся Вот я и спрашиваю, какая же из них лучше, в смысле определения простоты. |
||
Вернуться к началу | ||
s_e_r_g |
|
|
Очевидно, что основной критерий, дающий понять, какая из двух таблиц лучше - это время, которое затрачивается на определение простоты. На первый взгляд уже сразу видно, что простое деление должно работать быстрее, нежели определение НОД.
Оказалось, что по суммарному размеру обе таблицы практически одинаковы. Для верности надо проверить и прогнать тесты. |
||
Вернуться к началу | ||
swan |
|
|
s_e_r_g, откуда в этой задаче большие числа? Тем более очень большие числа?
|
||
Вернуться к началу | ||
s_e_r_g |
|
|
В этой задаче нет больших чисел.
В ней генерится таблица взаимно простых чисел, которая может быть использована для фильтрации чисел на простоту. Так вот: для фильтрации очень больших чисел такая таблица практически не работает |
||
Вернуться к началу | ||
swan |
|
|
Я не понимаю, что значит фильтрации чисел на простоту
|
||
Вернуться к началу | ||
s_e_r_g |
|
|
Я сейчас проверил свою гипотезу
Таблицу взаимно простых чисел можно использовать для тестирования натуральных чисел на простоту Она работает точно так же, как и обычная таблица простых чисел Я взял таблицу для n=1000 и проверил все числа, начиная с 1001 и до миллиона. Обычная таблица в диапазоне 1:1000 содержит 168 простых чисел, таблица взаимно простых чисел - 160 Обе таблицы дают совершенно одинаковый результат и находят одни и те же простые числа Только таблица взаимно простых чисел работает в 25 (!) раз медленнее обычной таблицы простых чисел И скорее всего, при увеличении размерности этих таблиц, это число будет только увеличиваться |
||
Вернуться к началу | ||
swan |
|
|
Я все-таки не понимаю, зачем все эти сложности.
Максимум что требуется - это список простых до 200000. Подмножество имеет вид: [math]\{p_1, p_2, \dots, p_k, s_1,s_2,\dots, s_m\}[/math] где [math]p_i[/math] - простые, [math]s_j[/math] - составные Составные имеют простой множитель, меньший [math]\sqrt N[/math]. Таким образом, у нас составных не более [math]\pi\left(\sqrt N\right)[/math] Далее эвристическое соображение (строго доказывать не хочется, но оно наверняка верно) Составное число имеет только один простой делитель, меньший [math]\sqrt N[/math]. Поскольку кол-во мест (составных) ограничено, то невыгодно занимать 2 стула - мы получим только одно число, меньшее [math]N[/math], а разделив эти простые - подберем из других свободных множителей 2 числа, пусть и меньших, чем первоначальное, но ненамного. Отсюда следует и что составное имеет максимум 2 различных простых делителя. Для каждой пары [math](p,q)[/math] с [math]pq<N[/math] посчитаем прибыль [math]w(p,q) = p^kq-p-q[/math], где k находится из соотношений [math]p^kq<N, p^{k+1}q>N[/math]. Также [math]w(p) = p^k-p[/math], где [math]p^k<N, p^{k+1}>N[/math]. Физический смысл прибыли понятен - насколько мы увеличиваем сумму по сравнению с суммой простых чисел, меньших N. Заметим, что можно не рассматривать пары [math](p,q)[/math], у которых [math]w(p,q)<w(p)[/math] Таким образом, задача сводится к поиску паросочетания на двудольном графе с максимальной прибылью, а это известная задача со множеством прописанных алгоритмов. (на самом деле, поскольку нижняя доля гораздо больше верхней - там практически проходит жадный алгоритм, но это другая история) |
||
Вернуться к началу | ||
swan |
|
|
На закуску - решение для [math]N=100[/math]
[math]\sqrt{100}=10[/math] Есть всего 4 простых числа, меньших 10: 2, 3, 5, 7 [math]w(2)=64-2=62[/math]. Только с двумя другими простыми прибыль будет больше. [math]\begin{matrix} q & 2 & 11 & 23 \\\hline s & 64 & 88 & 96 \\ w & 62 & 75 & 67 \end{matrix}[/math] [math]p=3[/math] [math]\begin{matrix} q & 3 & 11 \\\hline s & 81 & 99 \\ w & 78 & 85 \end{matrix}[/math] [math]p=5[/math] [math]\begin{matrix} q & 5 & 11 & 13 & 17 & 19 \\\hline s & 25 & 55 & 65 & 85 & 95 \\ w & 20 & 39 & 47 & 63 & 71 \end{matrix}[/math] [math]p=7[/math] [math]\begin{matrix} q & 7 & 11 & 13 \\\hline s & 49 & 77 & 91 \\ w & 42 & 59 & 71 \end{matrix}[/math] Для каждого p выбираем пару с максимальной прибылью: (2,11) + (3,11) + (5, 19) + (7, 13) У нас встретилась одна коллизия: (2,11) и (3,11) У p=2 следующая пара (2, 23) - прибыль уменьшается на 8. У p=3 следующая пара (3, 3) - прибыль уменьшается на 7. Значит выгоднее взять вместо (3,11) пару (3,3). Больше коллизий нет, поэтому выбранные пары обеспечивают максимум. 88, 81, 95, 91 + все остальные простые. |
||
Вернуться к началу | ||
swan |
|
|
s_e_r_g, раз уж вы вспомнили про эту задачу, скажите пож., Вам удалось получить ответ?
|
||
Вернуться к началу | ||
s_e_r_g |
|
|
Если вы имеете ввиду задачу : Максимальные подмножества взаимно простых чисел
то в общем случае я решения не нашел Я тогда ее бросил сразу, а сегодня вспомнил совсем случайно Мне надо разжевывать идеи, которые вы излагаете в сжатом виде |
||
Вернуться к началу | ||
На страницу Пред. 1, 2, 3, 4 След. | [ Сообщений: 32 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Конструкция бесконечного множества взаимно простых чисел
в форуме Теория чисел |
0 |
283 |
11 апр 2019, 09:52 |
|
Множество простых чисел и пар простых чисел-близнецов бескон
в форуме Размышления по поводу и без |
2 |
256 |
28 июн 2023, 11:23 |
|
Максимальное количество различных простых множителей
в форуме Теория чисел |
4 |
335 |
17 янв 2020, 13:14 |
|
Суммы взаимно простых | 11 |
844 |
27 апр 2015, 03:59 |
|
Суммы взаимно простых ч. 2 | 1 |
292 |
27 апр 2015, 21:31 |
|
Помощь с доказательством свойства взаимно простых многочлено
в форуме Линейная и Абстрактная алгебра |
4 |
157 |
19 май 2022, 22:06 |
|
Дан массив целых чисел. Найти максимальное число. Сделать в
в форуме Информатика и Компьютерные науки |
0 |
641 |
29 июн 2014, 14:02 |
|
Формула для простых чисел
в форуме Размышления по поводу и без |
30 |
1343 |
22 авг 2019, 23:30 |
|
Формула простых чисел
в форуме Теория чисел |
4 |
721 |
15 июл 2016, 08:01 |
|
Сумма простых чисел | 15 |
222 |
28 янв 2024, 10:52 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 13 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |