Как найти сомножители непростых нечётных чисел

[wrest]

Null в сообщении #1611017 писал(а):

Что-то типа решета Эратосфена будет быстрее. Это похоже на то что предлагает ТС.

Я не вижу где там надо раскладывать числа на множители.
Там надо:
1. Посчитать максимальное простое в разложении составных чисел из диапазона (оно равно следующему за целым корнем из верхней границы простому).
2. Сделать список простых от 3 до найденного простого (вот тут решето).
3. Поделить с остатком нижнюю границу диапазона на каждое удвоенное простое из списка п.2
4. Вычислить члены арифметических прогрессий с разностями из списка п.2

[ozheredov]

(Dedekind)

Dedekind в сообщении #1611137 писал(а):

Нет, там все очень печально, ни в какое сравнение с Вольфрамом.

Понял ((
А почему так? Я думал, там алгоритмы напрямую сворованы у Вольфрама

[wrest]

ivanovbp в сообщении #1610935 писал(а):

Ищем ННЧ с максимальным для диапазона сомножителем а = 19

Максимальный сомножитель для ННЧ из диапазона

ivanovbp в сообщении #1610935 писал(а):

для группы ННЧ от 381 до 507.

Равен 29, а не 19 (в том смысле, что таких чисел больше чем одно)...
ННЧ из диапазона от 381 до 507 которые делятся на 29:
$435=29\cdot 15$
$493=29\cdot 17$

-- 24.09.2023, 20:03 --

ivanovbp в сообщении #1610935 писал(а):

В диапазоне между квадратами двух соседних простых чисел ни одно ННЧ не может иметь один из сомножителей больше, чем левое простое число

Может, пример выше.

[Dmitriy40]

wrest
П.1 это вычисление максимально необходимого простого для решета Эратосфена.
П.2 это формирование списка простых для просеивания в решете Эратосфена.
П.3 это инициализация решета Эратосфена для просеивания не с нуля, а с указанного числа.
П.4 собственно и есть решето - вычёркивание составных чисел.
Последние три пункта (первый банальность) в сумме как раз и составляют решето Эратосфена для просеивания не с нуля, а в заданном диапазоне.
То что можно не вычёркивать составные числа (и даже не хранить список исходных чисел), а куда-то сохранять их делители (текущее простое по которому вычёркиваем), сути дела не меняет, это остаётся фактически тем же решетом. Со всеми присущими ему недостатками.
Попробуйте для развлечения так найти делители чисел в тысячном интервале для чисел из 20+ цифр (понадобится вычёркивать от примерно полумиллиарда простых). Особенно забавно когда в этом интервале будет число (или несколько) с двумя почти одинаковыми делителями, для нахождения которых придётся проверить как раз все эти полмиллиарда простых.

ADD.
Хотя 20+ цифр ещё не показательно, вот взять 30+ цифр, вот тогда уже да, проверять простые до 1e15, которых почти 30 триллионов, ну-ну, это на много часов. А факторизация (например эллиптическими кривыми) чисел из 30 цифр занимает доли секунды. Потому пока факторизовать надо не больше десятков тысяч чисел (учитывая что 99% из них имеют много достаточно малых делителей и быстро уменьшаются в процессе), то выгоднее именно индивидуальная факторизация, а не решето. Вот если нужны миллиардные интервалы ... Только зачем.

[wrest]

Dmitriy40
Да, что-то я тут вдруг решил поверить ТСу насчет

ivanovbp в сообщении #1610935 писал(а):

В диапазоне между квадратами двух соседних простых чисел ни одно ННЧ не может иметь один из сомножителей больше, чем левое простое число

А это оказалось не так
Я сперва подумал что речь о том, что на меньший делитель в разложении не может быть больше, но потом перечитал стартовый пост и понял, что ТС таки имеет в виду наибольший. А наибольший, вестимо, ограничен $b/3$ а не $nexprime(\sqrt{b})$ ($b$ - правый конец интервала).
Потом я ещё подумал , что ТСу надо минимум два числа с каждым делителем $q$ и нет придупал как это вычислять без переборов и факторизаций. В общем, в итоге я запутался и теперь не понимаю чего хотел ТС.
Так что главная канва рассуждения на смарку.

-- 24.09.2023, 20:19 --

Dmitriy40 в сообщении #1611157 писал(а):

Хотя 20+ цифр ещё не показательно,

Это явно выходит за рамки

ivanovbp в сообщении #1611065 писал(а):

Предложенный метод - для инженеров-расчётчиков, работающих "на земле", на большее не претендую.

и в частности

ivanovbp в сообщении #1611065 писал(а):

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

[Dedekind]

(Оффтоп)

ozheredov в сообщении #1611139 писал(а):

Понял ((
А почему так? Я думал, там алгоритмы напрямую сворованы у Вольфрама

Тут хз, я глубоко в это не вникал. Где-то пол года назад мне нужно было символьно решить пару каких-то простых диффур в ЧП. Sympy думал минут 10 на каждом и крашился в итоге, Вольфрам решил все за секунду. Но может с тех пор уже что-то там оптимизировали, я не проверял:)

[wrest]

Dmitriy40 в сообщении #1611157 писал(а):

Попробуйте для развлечения так найти делители чисел в тысячном интервале для чисел из 20+ цифр (понадобится вычёркивать от примерно полумиллиарда простых).

Да, конечно, когда интервалы сильно "узкополосные", лучше факторизовать каждое число в интервале, чем решетить их, тут я совершенно согласен.

[Dmitriy40]

wrest в сообщении #1611158 писал(а):

Это явно выходит за рамки

Озвученные ТС мотивы - вообще глупость, проще один раз заранее просчитать и тупо хранить списки или битовые массивы. Если вообще зачем-то хочется экономить микросекундное время выполнения практически любым методом (что на мой взгляд тоже глупость за очень редким исключением).

wrest в сообщении #1611162 писал(а):

Да, конечно, когда интервалы сильно "узкополосные", лучше факторизовать каждое чем решетить, тут я совершенно согласен.

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

[wrest]

Dmitriy40 в сообщении #1611165 писал(а):

проще один раз заранее просчитать и тупо хранить списки

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

[mihaild]

ivanovbp в сообщении #1611114 писал(а):

Поясните, что вам интересно

Каким образом Вы сделали вывод

ivanovbp в сообщении #1611065 писал(а):

Сразу видно, что вы никогда в жизни не занимались работой с конкретным "железом"

ivanovbp в сообщении #1611114 писал(а):

85 - не теоретически, а конкретно. И судить о том, где и когда появились калькуляторы, сподручнее мне

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

(Оффтоп)

ozheredov в сообщении #1611135 писал(а):

В общем да, но меня больше поразило существование sympy. Умеет ли он переплевывать Вольфрам?

Sympy пока что не претендует на конкуренцию с Вольфрамом. Конкурент Вольфраму - это скорее sage. Который местами лучше, местами хуже. У него адекватный синтаксис (в отличии от Вольфрама), и он умеет решать некоторые штуки, которые Вольфрам не умеет. Но Вольфрам по умолчанию умеет делать много разумных предположений, которые sage не делает.

wrest

ivanovbp в сообщении #1610935 писал(а):

В диапазоне между квадратами двух соседних простых чисел ни одно ННЧ не может иметь один из сомножителей больше, чем левое простое число

Да вроде это очевидная правда (кроме пары начальных интервалов): минимальное число, которое имеет простых сомножителей не меньше чем $p_n$, это $2^{p_n}$, что сильно больше чем $p_{n+1}^2$.

[wrest]

mihaild в сообщении #1611189 писал(а):

Да вроде это очевидная правда (кроме пары начальных интервалов):

Ну значит я не понял формулировку. "между квадратами двух соседних простых чисел" $19^2=361$ и $23^2=529$ полно нечетных составных чисел, в разложении которых имеются простые множители, большие чем "чем левое простое число" $19$, например

wrest в сообщении #1611156 писал(а):

ННЧ из диапазона от 381 до 507 которые делятся на 29:
$435=29\cdot 15$
$493=29\cdot 17$

Ну или $505=101 \cdot 5$

[mihaild]

wrest в сообщении #1611191 писал(а):

Ну значит я не понял формулировку. "между квадратами двух соседних простых чисел" $19^2=361$ и $23^2=529$ полно нечетных составных чисел, в разложении которых имеются простые множители, большие чем "чем левое простое число" $19$, например

А, похоже Вы правы, а я неправильно прочитал утверждение - я прочитал как "не может иметь сомножителей больше, чем левое простое число".
В правильном прочтении - да, между $p_n^2$ и $p_{n + 1}^2$ при $n > 1$ вообще всегда есть составные числа с простыми делителями большими $p_{n + 1}$: интервал имеет длину больше $2\cdot p_{n + 1}$, в интервале $(p_{n + 1}, 2 \cdot p_{n + 1} + 1]$ есть простое число, и в интервале $[p_n^2, p_{n + 1}^2]$ есть число, на него делящееся.

[Yadryara]

wrest в сообщении #1611158 писал(а):

В общем, в итоге я запутался и теперь не понимаю чего хотел ТС.
Так что главная канва рассуждения на смарку.

Вы так расстроились, что тоже заболели пробельной болезнью? На какую ещё смарку?

Что бросается в глаза сразу же, как только посмотришь на название темы?

"Как найти сомножители непростых нечётных чисел"

Что ещё за "непростые" числа? Человек не знает давно устоявшейся терминологии? Ведь чтобы людям было проще понимать, лучше пользоваться стандартной терминологией и говорить "составные".

Или ТС решил подчеркнуть что он включает в число "непростых" единицу(которая не является ни простым ни составным числом)?

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

Но проверять вроде всё-таки нужно.

[ivanovbp]

Караул!! Если бы ещё были волосы, выдрал бы их все!
В изложении темы допустил ошибку в разделе, касающемся промежуточных сомножителей, пункт г) :
перед скобкой (2$\cdot$17) отсутствует буква k Формулу следует читать так
$N_0$ = 289 + k$\cdot$(2$\cdot$17) = 289 + 3$\cdot$(2$\cdot$17)$ = 391
На цифровые данные ошибка не влияет, допущена при переносе с бумаги.

[mihaild]

Yadryara в сообщении #1611202 писал(а):

Что ещё за "непростые" числа? Человек не знает давно устоявшейся терминологии? Ведь чтобы людям было проще понимать, лучше пользоваться стандартной терминологией и говорить "составные".

Вообще "нечетные непростые числа" и "нечетные составные числа" по устоявшейся терминологии это немного разные множества, отличающиеся одним элементом. Для целей данной темы, впрочем, неважно.

Igadel в сообщении #1611217 писал(а):

Вы имеете ввиду, что $3<2^{\frac{2}{2}}$?

Да, в таком виде я сказал неправду, это верно только для достаточно больших $n$ (вроде бы при $n > 4$). Что собственно видно по тому что и вычитанное мной утверждение неверно: между $3^2$ и $5^2$ есть число с $4 > 3$ сомножителями.