Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 32 ]  На страницу Пред.  1, 2, 3, 4  След.
Автор Сообщение
 Заголовок сообщения: Re: Максимальное подмножество взаимно простых чисел
СообщениеДобавлено: 23 фев 2016, 10:42 
Не в сети
Последняя инстанция
Зарегистрирован:
14 июн 2011, 08:15
Сообщений: 3565
Cпасибо сказано: 50
Спасибо получено:
502 раз в 465 сообщениях
Очков репутации: 23

Добавить очки репутацииУменьшить очки репутации
s_e_r_g писал(а):
У этих обоих алгоритмов есть несколько общих недостатков
Во-первых, они обе не резиновые
Во-вторых, для проверки очень больших чисел и та, и другая не годятся


Вот я и спрашиваю, какая же из них лучше, в смысле определения простоты.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Максимальное подмножество взаимно простых чисел
СообщениеДобавлено: 23 фев 2016, 11:31 
Не в сети
Мастер
Зарегистрирован:
08 янв 2016, 15:28
Сообщений: 225
Cпасибо сказано: 2
Спасибо получено:
26 раз в 24 сообщениях
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
Очевидно, что основной критерий, дающий понять, какая из двух таблиц лучше - это время, которое затрачивается на определение простоты. На первый взгляд уже сразу видно, что простое деление должно работать быстрее, нежели определение НОД.
Оказалось, что по суммарному размеру обе таблицы практически одинаковы.
Для верности надо проверить и прогнать тесты.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Максимальное подмножество взаимно простых чисел
СообщениеДобавлено: 23 фев 2016, 11:34 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
s_e_r_g, откуда в этой задаче большие числа? Тем более очень большие числа?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Максимальное подмножество взаимно простых чисел
СообщениеДобавлено: 23 фев 2016, 11:42 
Не в сети
Мастер
Зарегистрирован:
08 янв 2016, 15:28
Сообщений: 225
Cпасибо сказано: 2
Спасибо получено:
26 раз в 24 сообщениях
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
В этой задаче нет больших чисел.
В ней генерится таблица взаимно простых чисел, которая может быть использована для фильтрации чисел на простоту.
Так вот: для фильтрации очень больших чисел такая таблица практически не работает

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Максимальное подмножество взаимно простых чисел
СообщениеДобавлено: 23 фев 2016, 11:52 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Я не понимаю, что значит фильтрации чисел на простоту

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Максимальное подмножество взаимно простых чисел
СообщениеДобавлено: 23 фев 2016, 15:58 
Не в сети
Мастер
Зарегистрирован:
08 янв 2016, 15:28
Сообщений: 225
Cпасибо сказано: 2
Спасибо получено:
26 раз в 24 сообщениях
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
Я сейчас проверил свою гипотезу
Таблицу взаимно простых чисел можно использовать для тестирования натуральных чисел на простоту
Она работает точно так же, как и обычная таблица простых чисел
Я взял таблицу для n=1000 и проверил все числа, начиная с 1001 и до миллиона.
Обычная таблица в диапазоне 1:1000 содержит 168 простых чисел, таблица взаимно простых чисел - 160
Обе таблицы дают совершенно одинаковый результат и находят одни и те же простые числа
Только таблица взаимно простых чисел работает в 25 (!) раз медленнее обычной таблицы простых чисел о_О
И скорее всего, при увеличении размерности этих таблиц, это число будет только увеличиваться

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Максимальное подмножество взаимно простых чисел
СообщениеДобавлено: 24 фев 2016, 19:01 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Я все-таки не понимаю, зачем все эти сложности.
Максимум что требуется - это список простых до 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]
Таким образом, задача сводится к поиску паросочетания на двудольном графе с максимальной прибылью, а это известная задача со множеством прописанных алгоритмов. (на самом деле, поскольку нижняя доля гораздо больше верхней - там практически проходит жадный алгоритм, но это другая история)

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Максимальное подмножество взаимно простых чисел
СообщениеДобавлено: 24 фев 2016, 19:03 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
На закуску - решение для [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 + все остальные простые.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Максимальное подмножество взаимно простых чисел
СообщениеДобавлено: 17 май 2019, 15:01 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
s_e_r_g, раз уж вы вспомнили про эту задачу, скажите пож., Вам удалось получить ответ?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Максимальное подмножество взаимно простых чисел
СообщениеДобавлено: 17 май 2019, 16:58 
Не в сети
Мастер
Зарегистрирован:
08 янв 2016, 15:28
Сообщений: 225
Cпасибо сказано: 2
Спасибо получено:
26 раз в 24 сообщениях
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
Если вы имеете ввиду задачу : Максимальные подмножества взаимно простых чисел
то в общем случае я решения не нашел

Я тогда ее бросил сразу, а сегодня вспомнил совсем случайно

Мне надо разжевывать идеи, которые вы излагаете в сжатом виде

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему    На страницу Пред.  1, 2, 3, 4  След.  Страница 3 из 4 [ Сообщений: 32 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Конструкция бесконечного множества взаимно простых чисел

в форуме Теория чисел

AndrejVolkov

0

283

11 апр 2019, 09:52

Множество простых чисел и пар простых чисел-близнецов бескон

в форуме Размышления по поводу и без

korolchukvasily

2

256

28 июн 2023, 11:23

Максимальное количество различных простых множителей

в форуме Теория чисел

IvanPetrovPRO

4

335

17 янв 2020, 13:14

Суммы взаимно простых

в форуме Интересные задачи участников форума MHP

lopkityu

11

844

27 апр 2015, 03:59

Суммы взаимно простых ч. 2

в форуме Интересные задачи участников форума MHP

lopkityu

1

292

27 апр 2015, 21:31

Помощь с доказательством свойства взаимно простых многочлено

в форуме Линейная и Абстрактная алгебра

Mark17

4

157

19 май 2022, 22:06

Дан массив целых чисел. Найти максимальное число. Сделать в

в форуме Информатика и Компьютерные науки

Nesquik60

0

641

29 июн 2014, 14:02

Формула для простых чисел

в форуме Размышления по поводу и без

Tirpa

30

1343

22 авг 2019, 23:30

Формула простых чисел

в форуме Теория чисел

Xenobius

4

721

15 июл 2016, 08:01

Сумма простых чисел

в форуме Интересные задачи участников форума MHP

MurChik

15

222

28 янв 2024, 10:52


Часовой пояс: UTC + 3 часа [ Летнее время ]



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

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


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

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved