Как писать быстрые программы

[Yadryara]

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

Тест простоты это не то же самое, что разложение числа на множители, одно другим не заменяется.

Если надо очень быстро выкидывать в мусорку множество кандидатов, то псевда ещё как пригождается.

Ещё раз внимательно посмотрел как сделано сейчас в программе. Конечно, эта псевда и так неслабо используется. Но навряд ли прям оптимально.

[wrest]

Yadryara
Вы задаёте туманные вопросы, если это конечно вопросы а не просто мысли вслух.
Конечно, если вам надо отбрасывать простые числа, то
if(ispseudoprime(n),next())
лучше чем
if(numdiv(n)==2, next())

[Yadryara]

wrest, контекст в последнее время один и тот же.

Нужно быстро определять, есть ли у числа (1е40-1e50) ровно 4, ровно 8 или же ровно 16 делителей. В противном случае отбрасывать. Можно считать, что это три разных задачи, для каждого количества делителей — своя.

[Dmitriy40]

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

Ещё раз внимательно посмотрел как сделано сейчас в программе. Конечно, эта псевда и так неслабо используется. Но навряд ли прям оптимально.

Мне ничего лучшего пока не придумалось. Для PARI. При своей реализации факторизации улучшения возможны, я выше уже даже их накидал.
Кроме того, ispseudoprime() используется и в самой factor() для установления что разложение завершено и наибольшее число простое.

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

Чем же ispseudorprime отличается от isprime ? Она же не пропускает какие-то простые ? Просто иногда (очень редко?) в придачу к ним хватает и составные.

Разными алгоритмами. И скоростью.
Да, ispseudoprime() может на какое-то составное сказать что оно простое (такие числа и называются псевдопростыми), но таких примеров мир ещё не видел и есть недоказанная гипотеза что такое и вовсе невозможно. И доказано прямой проверкой что до $2^{64}$ таких исключений точно нет. Простые она не пропускает, но не все числа что она заявила как простые реально простые (хотя исключений и не известно). Зато если сказала составное - точно составное, без исключений.

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

Нужно быстро определять, есть ли у числа (1е40-1e50) ровно 4, ровно 8 или же ровно 16 делителей. В противном случае отбрасывать.

Проверка простоты может различить два делителя и большее количество. Ничего более из проверки простоты не вытащить.

-- 29.11.2025, 12:59 --

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

Мне ничего лучшего пока не придумалось. Для PARI.

Точнее поулучшать можно попытаться, например разбить каждую общую проверку foreach(z0,d,...) на проверки сначала по pqrs, потом по pqr и лишь потом по pq (именно в таком порядке, невзирая на их вероятности) и ещё и перетасовать их с разными порогами между собой смотря как будет быстрее. Но не думаю что эффект будет большим.

[Yadryara]

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

Нужно быстро определять, есть ли у числа (1е40-1e50) ровно 4, ровно 8 или же ровно 16 делителей.

На всякий случай, вдруг люди не понимают. Реально пока решаются три упрощённых задачи: является ли то или иное число произведением двух (pq), трёх (pqr) или же четырёх (pqrs) различных простых чисел в первых степенях. Причём каждое из этих простых должно быть не меньше 67.

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

Точнее поулучшать можно попытаться, например разбить каждую общую проверку foreach(z0,d,...) на проверки сначала по pqrs, потом по pqr и лишь потом по pq (и ещё и перетасовать их с разными порогами между собой смотря как будет быстрее).

Это уже сделано. Правда, не так. Я проверяю согласно частотности, то есть сначала проверяю одну pq, затем три pqrs и лишь затем 17 pqr.

И с параметрами конечно играюсь.

Но, скорее всего, чего-то не учёл.

[Dmitriy40]

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

Я проверяю согласно частотности, то есть сначала проверяю одну pq, затем три pqr и лишь затем 17 pqr.

Мне кажется частотность/вероятность тут не совсем уместна: она не учитывает величину делителей, а factor() выполняются с ограничением на величину делителя. И думаю чем больше чисел требуется, тем вероятнее что они все кроме одного маленькие (меньше указанного порога). Несмотря на разную вероятность.
Запустите ту свою программу определения частотности, но дополнительно разбейте каждое число на группы по порогам из factor() и посмотрите как изменятся вероятности.

[wrest]

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

Нужно быстро определять, есть ли у числа (1е40-1e50) ровно 4, ровно 8 или же ровно 16 делителей. В противном случае отбрасывать.

Ну вот быстро тут определяется только что делителей больше двух (число составное). И если их больше двух, а число небольшое (<180 бит) то дальше только полная факторизация встроенным factor() или numdiv() если скрипт в pari/gp. Ну а откидывать числа по дополнительным условиям типа наименьший делитель больше порога (67) вы уже умеете.

[Dmitriy40]

Посчитал частотности (в штуках на 10000) для наименьшего делителя меньше порога:

Используется синтаксис Text

           kpod          p       pq      pqr     pqrs    pqrst      p2q      p2qr   p2qrs   p2qrst
10^40:    10000: [     861,    2523,    3060,    2196,     955,       1,       9,      13,       4]   1min, 59,899 ms
                 [       0,     592,    1476,    1552,     824,       1,       9,      13,       4]   <2^12
                 [       0,     157,     288,     205,      67,       0,       0,       0,       0]   <2^14
                 [       0,     197,     364,     199,      42,       0,       0,       0,       0]   <2^17
                 [       0,     173,     246,     136,      17,       0,       0,       0,       0]   <2^20
                 [       0,     183,     248,      68,       5,       0,       0,       0,       0]   <2^24
                 [     861,    1221,     438,      36,       0,       0,       0,       0,       0]   >2^24
           kpod          p       pq      pqr     pqrs    pqrst      p2q      p2qr   p2qrs   p2qrst
10^45:    10000: [     729,    2329,    3080,    2266,    1092,       2,       9,       8,       7]   6min, 55,747 ms
                 [       0,     513,    1431,    1555,     921,       2,       9,       8,       7]   <2^12
                 [       0,     132,     262,     195,      76,       0,       0,       0,       0]   <2^14
                 [       0,     153,     345,     229,      61,       0,       0,       0,       0]   <2^17
                 [       0,     117,     256,     124,      21,       0,       0,       0,       0]   <2^20
                 [       0,     146,     241,     101,      11,       0,       0,       0,       0]   <2^24
                 [     729,    1268,     545,      62,       2,       0,       0,       0,       0]   >2^24
           kpod          p       pq      pqr     pqrs    pqrst      p2q      p2qr   p2qrs   p2qrst
10^50:    10000: [     659,    2225,    2901,    2388,    1221,       1,       6,      10,       2]   20min, 26,544 ms
                 [       0,     495,    1246,    1569,     999,       1,       6,      10,       2]   <2^12
                 [       0,     109,     260,     236,     102,       0,       0,       0,       0]   <2^14
                 [       0,     143,     339,     227,      68,       0,       0,       0,       0]   <2^17
                 [       0,     108,     216,     146,      26,       0,       0,       0,       0]   <2^20
                 [       0,     121,     229,     108,      19,       0,       0,       0,       0]   <2^24
                 [     659,    1249,     611,     102,       7,       0,       0,       0,       0]   >2^24
           kpod          p       pq      pqr     pqrs    pqrst      p2q      p2qr   p2qrs   p2qrst

И для всех делителей меньше порога кроме наибольшего:

Используется синтаксис Text

           kpod          p       pq      pqr     pqrs    pqrst      p2q      p2qr   p2qrs   p2qrst
10^40:    10000: [     861,    2523,    3060,    2196,     955,       1,       9,      13,       4]   1min, 58,328 ms
                 [       0,     592,     205,      47,       8,       1,       3,       0,       0]   <2^12
                 [       0,     157,     104,      61,       8,       0,       0,       0,       0]   <2^14
                 [       0,     197,     199,      72,      34,       0,       0,       1,       0]   <2^17
                 [       0,     173,     195,     132,      41,       0,       0,       1,       1]   <2^20
                 [       0,     183,     273,     187,     120,       0,       0,       1,       1]   <2^24
                 [     861,    1221,    2084,    1697,     744,       0,       6,      10,       2]   >2^24
           kpod          p       pq      pqr     pqrs    pqrst      p2q      p2qr   p2qrs   p2qrst
10^45:    10000: [     729,    2329,    3080,    2266,    1092,       2,       9,       8,       7]   6min, 50,945 ms
                 [       0,     513,     200,      46,       3,       2,       3,       0,       0]   <2^12
                 [       0,     132,     106,      38,      14,       0,       0,       1,       0]   <2^14
                 [       0,     153,     148,      73,      26,       0,       0,       0,       0]   <2^17
                 [       0,     117,     151,      91,      32,       0,       0,       1,       0]   <2^20
                 [       0,     146,     217,     150,      65,       0,       0,       0,       1]   <2^24
                 [     729,    1268,    2258,    1868,     952,       0,       6,       6,       6]   >2^24
           kpod          p       pq      pqr     pqrs    pqrst      p2q      p2qr   p2qrs   p2qrst
10^50:    10000: [     659,    2225,    2901,    2388,    1221,       1,       6,      10,       2]   20min, 29,705 ms
                 [       0,     495,     156,      45,      10,       1,       0,       1,       0]   <2^12
                 [       0,     109,      84,      35,       8,       0,       0,       0,       0]   <2^14
                 [       0,     143,     130,      76,      31,       0,       0,       1,       0]   <2^17
                 [       0,     108,     119,      95,      29,       0,       1,       0,       0]   <2^20
                 [       0,     121,     193,     119,      73,       0,       1,       0,       1]   <2^24
                 [     659,    1249,    2219,    2018,    1070,       0,       4,       8,       1]   >2^24
           kpod          p       pq      pqr     pqrs    pqrst      p2q      p2qr   p2qrs   p2qrst

Вторая табличка почти аналогична коду программы, за исключением что не показаны случаи pqrsX, где все делители меньше порога, а оставшееся число X составное - такие случаи программой тоже отбраковываются.

[wrest]

Yadryara
Dmitriy40
Я нашёл место в коде факторизации pari/gp, где можно устроить ранний выход если уже найдено 4 делителя осталась нефакторизованная часть.
Любезный qwen написал дополнитльную функцию в ядро pari/gp которая будет возвращать количество простых делителей не превышающее заданное (например 4) или ноль если число не подходит. Но не сами делители (т.к. такая задача не стояла).
Ну Dmitriy40 это попробовать [пока] не может т.к. нужен линукс для пересборки pari
А вот Yadryara мог бы наверное потренироваться в новом деле сборки форка pari/gp Но надо бы сформулировать задачу для новой функции поточнее. Пока я понял так, что надо обязательно отбрасывать несвободные от квадратов числа. Плюс, надо отбрасывать числа у которых наименьший делитель больше какого-то порога. Сами простые делители не нужны, только их количество. Это все требования к новой функции на замену factor() или есть какие-то ещё?

[Yadryara]

Dmitriy40, Спасибо. Разбираюсь с Вашей таблицей.

wrest, Спасибо.

Давайте сразу упростим задачу. То есть пока будем заниматься только числами с 4-мя делителями.

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

Но надо бы сформулировать задачу для новой функции поточнее. Пока я понял так, что надо обязательно отбрасывать несвободные от квадратов числа.

Да, конечно. Иначе 4-х делителей не видать. А вот кубы можно не отбрасывать. Но их очень мало, поэтому можно пока не принимать во внимание, а искать только числа вида pq.

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

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

Нет, наоборот. Надо отбрасывать числа, которые меньше 67. Кстати, не спросил, надеюсь у Дмитрия в таблице как раз такой порог. То есть $p\geqslant 67$ и $p< q \geqslant 71 $.

[wrest]

Yadryara
Если вам такая функция нужна, то придется потратить ваше время.
Результат не гарантирован, будет ли заметно ускорение - тоже не ясно.

В общих чертах, будет использована "машинерия" факторизации pari/gp с остановкой по достижению условий.

Нужно будет скачать исходный код pari/gp, изменить его и пересобрать pari/gp

Мигните, если готовы

[Yadryara]

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

Нужно будет скачать исходный код pari/gp, изменить его и пересобрать pari/gp

Звучит страшно. Опять сотни мегов качать?

-- 29.11.2025, 20:52 --

wrest

И кстати, какую функцию будем делать? Нужно найти 1 число с 4 делителями, 17 чисел с 8 делителями и 3 числа с 16-ю делителями. Может, раз дело такое серьёзное, 8 делителями заняться? Чтоб ради одного числа пока не париться.

[wrest]

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

И кстати, какую функцию будем делать?

Это я у вас и спрашивал:

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

надо бы сформулировать задачу для новой функции поточнее.

[Yadryara]

Можно ещё точнее. Или уж тогда задавайте уточняющие вопросы.

Сколько всего способов собрать 4 делителя?

1. $p^3$
2. $pq$

Сколько всего способов собрать 8 делителей?

1. $p^7$
2. $p^3q$
3. $pqr$

Сколько всего способов собрать 16 делителей?

1. $p^{15}$
2. $p^7q$
3. $p^3q^3$
4. $p^3qr$
5. $pqrs$

Для последних способов:

$p$, $q$, $r$, $s$ — простые числа, причём $67 \leqslant p < q < r < s$.

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

[Dmitriy40]

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

Кстати, не спросил, надеюсь у Дмитрия в таблице как раз такой порог. То есть $p\geqslant 67$ и $p< q \geqslant 71 $.

Да, $67 \leqslant p < q < r < s$.

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

$67 \leqslant p < q < r < s$.

Вот это $p < q < r < s$ про $p$ не обязательно, могут быть три малых делителя и большой в квадрате. Исключительно редко, но может.

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

предлагаю пока ограничиться первыми степенями простых

Поддерживаю.

wrest
Достаточно если вернётся флаг точного равенства количества делителей указанному n и 0 если такое равенство недостижимо. До конца разлагать при этом не нужно, после получения n-1 делителей если осталось составное число, возвращать 0. И если разложилось до конца (последнее число простое), но n делителей не вышло, тоже возвращать 0. При обнаружении степени выше 1 сразу возвращать 0.
Фактически надо просто добавить один if с парой-тройкой условий внутрь factor() около проверки оставшегося числа не простоту в конце цикла поиска делителей. Я вероятно даже код могу написать, но не проверить.
Функцию удобно назвать isnumdivn(x,n) - флаг что numdiv(x)=n. Или factorn1(x,n) если возвращать таки вектор делителей или 0 если их точно не n штук в первых степенях.