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

[ivanovbp]

для wrest
В моих тексте и сообщениях всегда имею в виду левый сомножитель. И если он "максимальный", то только среди других левых сомножителей диапазона. Правый сомножитель, действительно, может быть больше левого в разы, но речь не о нём.
Общее замечание:
Дались же вам миллиарды и триллионы! Инженер-технарь ( для wrest , похоже, это низшая каста) редко имеет дело с такими порядками. Жаль только, что они не посещают столь изысканные форумы.

[mihaild]

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

[Dmitriy40]

ivanovbp
Я присоединюсь и даже выделю жирным самое важное:

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

Покажите мне хоть одного человека, которому нужно раскладывать на простые множители десяток идущих подряд чисел порядка нескольких тысяч, не имеющего доступа к вычислительной технике.

Любой технике, начиная от калькулятора (можно и даже без корня). Потому что даже калькулятором проще разложить на множители перебором простых делителей (тем более что признаки делимости на 2,3,5 тривиальные и сразу отсеивают 73% чисел).

[wrest]

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

Инженер-технарь ( для wrest , похоже, это низшая каста) редко имеет дело с такими порядками. Жаль только, что они не посещают столь изысканные форумы.

Дело не в изысканности форумов. Дело в микросекундах, за которые компьютер факторизует тысячи чисел.
"Компьютер" тут употребляется условно. Современный телефон (смартфон) тоже факторизует за миллискунды. Собсно программа, которую я привёл, работает как раз на смартфоне -- любой (почти) инженер-технарь может её запустить (да и написать тоже).

Ещё я честно сказать так и не понял о чём вообще сыр-бор и где новизна. То есть, какая задача решалась отличным образом до того как вы написали на форум. То что я понял, это: задача разделить все нечётные числа из данного интервала на классы в соответствии с наименьшими простыми множителями, входящими в разложение, от 3 до наибольшего из наименьших, при условии что множителей больше одного.
При тех масштабах что вы предлагаете, на мой взгляд лучше всего делать как я написал: делить начало интервала с остатком и так находить первый член прогрессии. Тогда не надо ничего перебирать, это прямые вычисления, и скажем при делении столбиком (если делить "вручную") частное и остаток получаются самым естественным образом.

-- 25.09.2023, 19:02 --

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

В моих тексте и сообщениях всегда имею в виду левый сомножитель.

А написано было не так:

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

ни одно ННЧ не может иметь один из сомножителей больше, чем

Написано "один из" а не "левый" Ну это разъяснилось теперь, хорошо.

[wrest]

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

Тогда не надо ничего перебирать, это прямые вычисления, и скажем при делении столбиком (если делить "вручную") частное и остаток получаются самым естественным образом.

ivanovbp
В качестве иллюстрации, вот расчет на бумажке всех нечетных чисел из диапазона от 1379 до 1651 которые делятся на 23. Заметьте: никаких переборов, никакого калькулятора, никаких "сложностей" в виде изменения алгоритма, разностей квадратов и т.п., просто последовательное вычисление:

[ivanovbp]

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

vanovbp
В качестве иллюстрации, вот расчет на бумажке всех нечетных чисел из диапазона от 1379 до 1651 которые делятся на 23. Заметьте: никаких переборов, просто последовательное вычисление:

1. Не останавливайтесь на достигнутом, найдите сомножители для всех ННЧ выбранного вами диапазона
2. О сути предложенного метода ("кому-то нравится поп, а кому-то поповская дочка") : конечно, можно и перебором, и тестами прочих Агравалов. Предлагаемый метод - лишь один из многих, на мой взгляд, несложный и не занимающий много времени

[Dmitriy40]

wrest
3-й шаг лишний, проще в 4-м сделать ещё итерацию (хотя бы в уме) и убедиться что 7-е число превышает $b$.
Если же хочется заранее знать примерное количество чисел в прогрессиях, то один раз заранее вычислить $c=(b-a)/2=(1651-1379)/2=136$ и потом делить $c=136$ на текущее простое $p=23$ (или любое другое). Погрешность уж точно не превысит $2$ (на самом деле $1$), вполне нормально для оценки.

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

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

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

[wrest]

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

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

Так я же и нашел, в посте post1611131.html#p1611131 все они перечислены (надо нажать на слово "Оффтоп" и всё раскроется). И это не мной выбран диапазон, а вами, вот тут:

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

Попробуйте иначе найти сомножители для всех ННЧ, скажем, от 1379 до 1651. Интересно, сколько времени это займёт?

Я не очень понимаю ваш сарказм, т.к. я искренне хотел понять пользу от вашей придумки...

[ivanovbp]

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

[miflin]

(Оффтоп)

Осчастливить человечество - ох, как непросто.
Не понимает оно своего щастя, неблагодарное.

[wrest]

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

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

Сравните ваше:

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

3. Ищем ННЧ с сомножителем а = 17
а) обозначу как m разность между квадрами ПЧ 19 и 17, т.е. m = $19^2$ - $17^2$ = 361 - 289 = 72
б) введем число k = m / (2$\cdot$17) = 72 / (34) = 2, 117.....,.,.,
в) округляем k до целого числа, т.е. принимаем k = 3
г) определяем $N_0$ как $N_0$ = 289 + (2$\cdot$17) = 391

С моим:
1. Находим остаток от деления левого конца интервала 381 на удвоенный множитель (17+17=34). В данном случае, делаем это "в уме", остаток равен 7.
2. Определяем $N_0$ так: вычитаем из 381 остаток 7 и прибавляем множитель 17, получаем $N_0=381-7+17=391$
Вам не кажется ваше рассуждение чесанием левой ногой правого уха, в сравнении с моим рассуждением?

[Dmitriy40]

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

[wrest]

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

Ну и в чём тогда новизна или практическая польза?

Я так понял что ТС решал задачу максимизации коэффициента заполнения при упаковке многих маленьких прямоугольников в один большой, и если бы у него тогда был этот метод, задача решалась бы проще и быстрее. А может он ещё тогда и научился паковать, а написал об этом вот только сейчас, чтобы знание кому-то пригодилось.

[ivanovbp]

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

Сравните ваше
С моим:
1. Находим остаток от деления левого конца интервала 381 на удвоенный множитель (17+17=34). В данном случае, делаем это "в уме", остаток равен 7.
2. Определяем $N_0$ так: вычитаем из 381 остаток 7 и прибавляем множитель 17, получаем $N_0=381-7+17=391$
Вам не кажется ваше рассуждение чесанием левой ногой правого уха, в сравнении с моим рассуждением?

Убедили, беру свои слова обратно. Можно и по-вашему