2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3, 4  След.
 
 Re: Распределение простых чисел
Сообщение18.12.2012, 12:15 
Зачем такие страсти.
Не лучше ли брать суммы логарифмов или последовательные отношения простых чисел.

 
 
 
 Re: Распределение простых чисел
Сообщение18.12.2012, 12:23 
Аватара пользователя
Смотря в чём делаем. В Си, вероятно, лучше с логарифмами (хотя бы потому, что сами числа не влезут в long long).

 
 
 
 Re: Распределение простых чисел
Сообщение18.12.2012, 12:34 
В любом случае вычислений гораздо меньше.

 
 
 
 Re: Распределение простых чисел
Сообщение18.12.2012, 12:38 
Cash в сообщении #660105 писал(а):
Не понадобятся никакие отсечения. Venco же уже все написал. Делим массив пополам. Для каждого подмножества первой части (которых чуть больше миллиона) подбираем за 20 сравнений добавку из второй части. Все выполняется за секунду.
То ли туплю, то ли... сильно туплю :-(
Добавку до чего?

 
 
 
 Re: Распределение простых чисел
Сообщение18.12.2012, 12:45 
Аватара пользователя
У нас миллион множителей, составленных из первых 20 простых, и миллион же - из вторых 20. Мы перебираем первый миллион (идя снизу; они оба отсортированы), и к каждому множителю подбираем пару из второго массива, которая его ставит как можно ближе к $\sqrt n$.

 
 
 
 Re: Распределение простых чисел
Сообщение18.12.2012, 13:16 
ИСН в сообщении #660123 писал(а):
У нас миллион множителей, составленных из первых 20 простых, и миллион же - из вторых 20. Мы перебираем первый миллион (идя снизу; они оба отсортированы), и к каждому множителю подбираем пару из второго массива, которая его ставит как можно ближе к $\sqrt n$.

Спасибо! Вроде, въехал. Мне почему-то сразу померещилось, что такой метод не гарантирует оптимума. Призадумался, гарантирует.

Но тут же вопрос: а сортировать быстрой сортировкой? Или как-то использовать изначальную отсортированность множителей?

 
 
 
 Re: Распределение простых чисел
Сообщение18.12.2012, 13:21 
Аватара пользователя
Сортировать - как хотите. Я цинично воспользовался встроенной функцией, не заботясь о том, что у неё внутри.

 
 
 
 Re: Распределение простых чисел
Сообщение18.12.2012, 13:27 
А отсекать для ускорения процесса все же можно. Из произведений (сумм логарифмов) бОльших чисел оставить только не превышающие квадратного корня и наименьшее из превышающих.

 
 
 
 Re: Распределение простых чисел
Сообщение18.12.2012, 14:45 
У нас миллион множителей, составленных из первых 20 простых, и миллион же - из вторых 20. Мы перебираем первый миллион (идя снизу; они оба отсортированы), и к каждому множителю подбираем пару из второго массива, которая его ставит как можно ближе к .

Хотелось бы увидеть математическую модель программы на примере первых простых чисел 2 3 5 7 11 13 17. Это бы всё объяснило в подробностях. Заранее спасибо

 
 
 
 Re: Распределение простых чисел
Сообщение18.12.2012, 15:03 
Аватара пользователя
Эххх.... Ну поехали.
Призведение всех простых будет 510510. Корень из него - около 714.5.
В левый массив отправляем 2, 3, 5, 7. В правый - остальные.
Собираем и сортируем все возможные произведения в каждом массиве.
Левый: 1, 2, 3, 5, 6, 7, 10, 14, 15, 21, 30, 35, 42, 70, 105, 210.
Правый: 1, 11, 13, 17, 143, 187, 221, 2431.
Берём из левого массива число 1. На какое число из правого массива его надо умножить, чтобы максимально приблизиться к корню снизу?

 
 
 
 Re: Распределение простых чисел
Сообщение18.12.2012, 15:36 
221 так как 2431 уже больше корня. А дальше?

В левый массив отправляем 2, 3, 5, 7. В правый - остальные.
Всегда надо делить числа пополам или это случайность. Как они будут распределены в этих двух массивах и почему

 
 
 
 Re: Распределение простых чисел
Сообщение18.12.2012, 15:51 
Аватара пользователя
Дальше запоминаем достигнутый оптимум (221) и переходим к числу 2. Для него тот же самый вопрос (на какое число из правого массива...)
Я не делил числа пополам, да и как бы я поделил пополам, когда их 7? Распределены в этих двух массивах они будут так, как старшина сказал. Если Вы понимаете метод, то можете исследовать и оптимизировать эти вопросы, и таким образом выиграть ещё какое-то маргинальное улучшение. По-моему, это не нужно.

 
 
 
 Re: Распределение простых чисел
Сообщение18.12.2012, 16:37 
То есть в данном примере Мы будем продолжать операцию пока не получим число 42 из первого столбика и число 17 из второго столбика?

 
 
 
 Re: Распределение простых чисел
Сообщение18.12.2012, 16:42 
Аватара пользователя
Да, так. Это плохой пример - в типичном случае мы будем продолжать до конца, чтобы убедиться, что там ничего лучшего не найдётся.

 
 
 
 Re: Распределение простых чисел
Сообщение18.12.2012, 16:54 
Плохой потому , что число 714 максимально близко подошло к корню и мы можем быть уверены , что лучше уже не будет?

 
 
 [ Сообщений: 50 ]  На страницу Пред.  1, 2, 3, 4  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group