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

[ИСН]

Nacuott в сообщении #659966 писал(а):

...произведение половины чисел менее всего отличающееся от полученного числа, после извлечения корня.

Плохая идея, во-первых, потому что 20 чисел из 40 можно выбрать довольно многими способами, а во-вторых, потому что искомый набор может не быть (и не будет) состоящим ровно из 20 чисел.

-- Вт, 2012-12-18, 01:04 --

wcl.AleX, Вам надо было сказать последние 9 цифр и спросить остальные, а так я могу только констатировать, что таки да, результат для 35 у меня получается такой же.

-- Вт, 2012-12-18, 01:05 --

venco в сообщении #659911 писал(а):

3) заранее посчитать и отсортировать все возможные наборы из некоторого количества последних множителей (чтобы потом использовать бинарный поиск).

Ключевая идея вот. А первые две я вообще не использовал.

[VAL]

wcl.AleX в сообщении #659956 писал(а):

Квадратов между чем и чем? Покажите, пожалуйста, на примере , без двойки, с числами 3,5,7,11,13
Числа должны быть 105 и 143

$123^2$- самый маленький квадрат, превосходящий $a=3\cdot5\cdot7\cdot11\cdot13$.
$123^2-a$ не является полным квадратом. Но уже $124^2-a=19^2$.
Отсюда $a=(124-19)(124+19)$.

[Nacuott]

Ну, не половины, но до тех пор, пока произведение ближе всего не приблизится к извлеченному квадрату.

[ИСН]

А это перебирать порядка $2^{40}$, что немного чересчур.

[wcl.AleX]

Уважаемый Val, ваш способ эффективен только до первых 20 простых чисел, а мне нужно от 40
проблема с двойкой решается элементарно, но к сожалению это не решает задачу в целом, так как всё равно нельзя использовать более 40 чисел


заранее посчитать и отсортировать все возможные наборы из некоторого количества последних множителей (чтобы потом использовать бинарный поиск).
Можно увидеть программу в си?

[ИСН]

А Вам тогда какая часть работы останется?

[Батороев]

VAL в сообщении #659974 писал(а):

$123^2$- самый маленький квадрат, превосходящий $a=3\cdot5\cdot7\cdot11\cdot13$.
$123^2-a$ не является полным квадратом. Но уже $124^2-a=19^2$.
Отсюда $a=(124-19)(124+19)$.

Это фактически повторяет "факторизацию числа по Ферма" (в данном случае число - примориал). Метод Ферма позволяет в первую очередь находить натуральные множители числа, наименее отличающиеся друг от друга (независимо от числа их простых множителей и наличия среди них простого 2).
По-видимому, лучшего способа решить поставленную задачу (независимо от величины примориала), чем этот, не найти.

[ИСН]

Пруф или фуфло.

-- Вт, 2012-12-18, 11:11 --

(Много раскрывать не надо, дайте две следующие цифры с конца)

[Батороев]

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

Пруф или фуфло.

Любое натуральное число $N=ab$ можно разложить на разность квадратов:
$N=\left(\dfrac{a+b}{2}\right)^2-\left(\dfrac{a-b}{2}\right)^2$*
Из этого выражения видно, что $\left(\dfrac{a+b}{2}\right)^2>N$, соответственно: $\left(\dfrac{a+b}{2}\right)>\sqrt {N}$.
Чем меньше выражение $\left(\dfrac{a-b}{2}\right)^2$, тем менее $\left(\dfrac{a+b}{2}\right)$ превосходит $\sqrt {N}$.
Таким образом, факторизируя число по методу Ферма, первыми обнаружатся множители $a,b$ наименее отличающиеся друг от друга.
*Т.к. примориалы имеют четность степени $2^1$, то следует оперировать квадратами чисел, имеющих $5$ после запятой.

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

(Много раскрывать не надо, дайте две следующие цифры с конца)

Программированием, к сожалению не владею, поэтому "пасс".

[VAL]

Батороев в сообщении #660070 писал(а):

VAL в сообщении #659974 писал(а):

$123^2$- самый маленький квадрат, превосходящий $a=3\cdot5\cdot7\cdot11\cdot13$.
$123^2-a$ не является полным квадратом. Но уже $124^2-a=19^2$.
Отсюда $a=(124-19)(124+19)$.

Это фактически повторяет "факторизацию числа по Ферма" (в данном случае число - примориал).

Разумеется.

Цитата:

Метод Ферма позволяет в первую очередь находить натуральные множители числа, наименее отличающиеся друг от друга

Как раз то, что нам нужно.

Цитата:

(независимо от числа их простых множителей и наличия среди них простого 2).

Нет, двойка в нечетной степени мешает. Но эта беда легко исправляется.

Цитата:

По-видимому, лучшего способа решить поставленную задачу (независимо от величины примориала), чем этот, не найти.

Угу.
Осталось выяснить, почему ИСН, давно нашел ответ. А я, своим "лучшим способом" час мурыжил комп и снял задачу.
(Зато программку писал одну минуту )
Конечно, можно существенно усовершенствовать метод Ферма, используя систему попарно взаимно простых модулей, дабы не пытаться миллиард раз проверять, является ли число квадратом. Но от самого миллиарда итераций все равно не уйти.
Так что, лучшим с практической точки зрения является комбинированный метод с отсечением бесперспективных ветвей и т.д.

[ИСН]

Это всё и так очевидно. Я просил пруфов к

Батороев в сообщении #660070 писал(а):

По-видимому, лучшего способа решить поставленную задачу (независимо от величины примориала), чем этот, не найти.

Нет пруфов? Так и запишем.

[Батороев]

Мдя! А вроде бы казалось, что по методу Ферма комп должен быстро найти - все-таки, аж 40 множителей! Ладно, след. раз креститься буду!

[VAL]

Батороев в сообщении #660099 писал(а):

Мдя! А вроде бы казалось, что по методу Ферма комп должен быстро найти - все-таки, аж 40 множителей! Ладно, след. раз креститься буду!

Тут еще от везения многое зависит.
Для уже упомянутого случая 35-ти простых, по методу Ферма мой комп тратит около сотой доли секунды. Просты искомые произведения очень близки и находятся всего за 6383 итерации.

[Cash]

VAL в сообщении #660095 писал(а):

Так что, лучшим с практической точки зрения является комбинированный метод с отсечением бесперспективных ветвей и т.д.

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

[ИСН]

Вот-вот. Даже бинарный поиск не нужен: мы тупо идём по левому массиву снизу, а по правому - сверху.