Распределение простых чисел

[vorvalm]

Зачем такие страсти.
Не лучше ли брать суммы логарифмов или последовательные отношения простых чисел.

[ИСН]

Смотря в чём делаем. В Си, вероятно, лучше с логарифмами (хотя бы потому, что сами числа не влезут в long long).

[vorvalm]

В любом случае вычислений гораздо меньше.

[VAL]

Cash в сообщении #660105 писал(а):

Не понадобятся никакие отсечения. Venco же уже все написал. Делим массив пополам. Для каждого подмножества первой части (которых чуть больше миллиона) подбираем за 20 сравнений добавку из второй части. Все выполняется за секунду.

То ли туплю, то ли... сильно туплю
Добавку до чего?

[ИСН]

У нас миллион множителей, составленных из первых 20 простых, и миллион же - из вторых 20. Мы перебираем первый миллион (идя снизу; они оба отсортированы), и к каждому множителю подбираем пару из второго массива, которая его ставит как можно ближе к $\sqrt n$.

[VAL]

ИСН в сообщении #660123 писал(а):

У нас миллион множителей, составленных из первых 20 простых, и миллион же - из вторых 20. Мы перебираем первый миллион (идя снизу; они оба отсортированы), и к каждому множителю подбираем пару из второго массива, которая его ставит как можно ближе к $\sqrt n$.

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

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

[ИСН]

Сортировать - как хотите. Я цинично воспользовался встроенной функцией, не заботясь о том, что у неё внутри.

[VAL]

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

[wcl.AleX]

У нас миллион множителей, составленных из первых 20 простых, и миллион же - из вторых 20. Мы перебираем первый миллион (идя снизу; они оба отсортированы), и к каждому множителю подбираем пару из второго массива, которая его ставит как можно ближе к .

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

[ИСН]

Эххх.... Ну поехали.
Призведение всех простых будет 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. На какое число из правого массива его надо умножить, чтобы максимально приблизиться к корню снизу?

[wcl.AleX]

221 так как 2431 уже больше корня. А дальше?

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

[ИСН]

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

[wcl.AleX]

То есть в данном примере Мы будем продолжать операцию пока не получим число 42 из первого столбика и число 17 из второго столбика?

[ИСН]

Да, так. Это плохой пример - в типичном случае мы будем продолжать до конца, чтобы убедиться, что там ничего лучшего не найдётся.

[wcl.AleX]

Плохой потому , что число 714 максимально близко подошло к корню и мы можем быть уверены , что лучше уже не будет?