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

[Yadryara]

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

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

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

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

Именно поэтому и написал:

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

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

То есть для первых степеней.

[wrest]

Yadryara
Мы тут говорим о том, что

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

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

и

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

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

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

Вы, надеюсь, понимаете смысл вопроса "какие требования к функции?"
Он означает, что надо описать входные данные. Очевидно - тестируемое число плюс какие-то (какие?) параметры, и выходные данные (возвращаемые).

-- 29.11.2025, 22:51 --

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

Достаточно если вернётся флаг точного равенства количества делителей

Всего или простых? numdiv() или omega() ?

-- 29.11.2025, 22:59 --

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

Я вероятно даже код могу написать, но не проверить.

Пока предложение такое:

1. /* Возвращает: 
2.    k = omega(n), если omega(n) <= m 
3.    0, если omega(n) > m 
4. */ 
5.  
6. long 
7. omega_upto(GEN n, long m) 
8. { 
9.   pari_sp av = avma; 
10.   long nb = 0; 
11.   GEN part, here; 
12.  
13.   if (typ(n) != t_INT || signe(n) <= 0) return -1; 
14.   if (cmpiu(n, 1) <= 0) return 0; 
15.  
16.   part = ifac_start(n, 0);  // обычный режим 
17.  
18.   for (;;) 
19.   { 
20.     here = ifac_main(&part); 
21.     if (!here) break; 
22.  
23.     nb++; 
24.     if (!equali1(EXPON(here))) { 
25.         // если нужны ТОЛЬКО бесквадратные, можно вернуть 0 
26.         // но если вас интересует просто omega(n), игнорируем степени 
27.           set_avma(av);  
28.       return 0;  // ранний выход 
29.     } 
30.     if (nb > m) { 
31.       set_avma(av);  
32.       return 0;  // ранний выход 
33.     } 
34.     ifac_delete(here); 
35.   } 
36.  
37.   set_avma(av); 
38.   return nb;  // return number of distincs prime factors 0 <= nb <= m  
39. } 

Дописывать в src/basemath/ifactor1.c ну и в заголовки

[Yadryara]

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

Очевидно - тестируемое число плюс какие-то (какие?) параметры,

Уже сказал какие параметры. Ещё раз:

На вход подаётся 17 чисел. И все до единого должны иметь ровно 8 делителей.

Кроме того:

На вход подаётся 3 числа. И все должны иметь ровно 16 делителей.

На вход подаётся 1 число. Оно должно иметь ровно 4 делителя.

И ещё:

На вход подаётся 1 число. Оно должно иметь ровно 2 делителя.

Итого 22 числа. Если хоть одно из них имеет другое количество делителей — цепочка не соберётся.

Выходные данные — какой-нибудь флаг успех/провал.

[Dmitriy40]

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

Сейчас вы делаете это при помощи функции factor() которая производит факторизацию полностью

Нет, сейчас это делается factor(x,2^15) и анализом что она вернула. Если делителей больше n, то кортеж отбрасываем. Если длина вектора ровно n и последнее число составное - кортеж отбрасываем (делителей точно больше n). Если длина n и последнее число простое - ок, разложение завершено. Иначе продолжаем проверку других чисел (мест кортежа).

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

Всего или простых? numdiv() или omega() ?

Вообще говоря всего, numdiv().
Но раз уж ограничиваемся только первыми степенями, то одно пересчитывается в другое: numdiv(x)=2^omefa(x).

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

На вход подаётся 17 чисел.

Хм, я говорил про замену лишь numdiv() или factor(), без списка чисел ...

wrest
ОК, пусть будет вектор чисел и требуемое число делителей (хоть простых, хоть всего, лучше таки второе для универсальности). Типа isnumdivs([],n)={0,1}.
Возвращать можно просто флаг что все они имеют ровно столько делителей (и 0 в любом другом случае). Максимально быстро. Оптимизировать по скорости возврата 0, не 1.
Но это на порядок сложнее модификации лишь factor() или numdiv().

-- 29.11.2025, 23:09 --

Или даже такую: isnumdiv_2_4_8_16([], [], [], []) - вектора для 2,4,8,16 делителей (могут быть и пустыми).

[Yadryara]

Я тоже про флаг уже сказал. Я просто пытаюсь разными способами объяснить.

А у Вас, кстати, регулярная ошибка:

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

Если делителей больше n, то кортеж отбрасываем.

И здесь и дальше стоило говорить не количество делителей, а количество различных простых в разложении.

$pqrs$

Количество делителей — 16.
Количество различных простых в разложении — 4.

[wrest]

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

ОК, пусть будет вектор чисел

Ненене, это слишком, имхо. Под одно число там всё готово (в коде). А вектор...

[Dmitriy40]

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

А у Вас, кстати, регулярная ошибка:

Это не ошибка, я понимаю что смешиваю два понятия, впрочем рискуя и сам запутаться.
Но считаю что numdiv() (количество делителей) лучше #(factor()[,1])=omega() (количество простых делителей) - более универсально и позволяет прозрачно добавить потом и обработку редких случаев.

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

Ненене, это слишком, имхо. Под одно число там всё готово (в коде). А вектор...

Да тоже без проблем, просто добавить параметры в функцию и цикл внутрь (это важно!) вот этого вашего for(;;). И при обнаружении первой же ошибки сразу выходить, не проверяя остальные.

-- 29.11.2025, 23:23 --

И кстати вместо isnumdiv_2_4_8_16([], [], [], []) лучше isnumdivs([], []) - числа из первого вектора должны иметь ровно делителей из второго вектора.

[wrest]

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

[wrest]

А нет, вроде победил
Вот новая функция в сравнении с factor() на 50-значных числах
? for(i=1,10^3,omega_upto(10^50+random(10^7),4,0))
time = 33,433 ms.
? f=0;for(i=1,10^3,f=factor(10^50+random(10^7)))
time = 1min, 16 ms.
?

[Yadryara]

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

numdiv() или omega() ?

О, как. Оказывается есть просто омега. О! Мега!

А ведь у VAL в коде было matsize(g)[1].

И я ещё думал что за математический размер такой. Оказалось размер матрицы. И обозначил у себя Количество УНикальных Простых:

kunp=matsize(fac)[1];

Но это kunp, видимо, для любого числа можно и без фактора получить. Попросту omega(число). Будет ли это быстрее, надо тестить. То есть прогонять через тестя. А где ж его взять-то.

[Yadryara]

wrest, хочется поздравить, но рановато.

Надо же сначала понять что же считает ваша функция.

omega_upto(10^50+random(10^7),4,0)

Судя по названию, она отбирает числа, у которых ровно 4 различных простых делителя? А для остальных возвращает 0?

Но тут обнаружил у Паришной омеги неприятное свойство:

(08:05) gp > omega(420)
%1 = 4
(08:05) gp > omega(210)
%2 = 4
(08:05) gp > omega(2310)
%3 = 5
(08:06) gp > omega(18480)
%4 = 5
(08:06) gp > omega(6930)
%5 = 5

То есть она считает количество различных простых делителей в любой степени. А нам нужно чтобы все они были именно в первой степени.

Может это и не страшно, пусть считает с запасиком, лишь бы быстро было. Всё равно степени выше первой довольно-таки редки.

Да, матсайз с фактором считают то же самое, что и омега:

(08:19) gp >  matsize(factor(2310))[1]
%7 = 5
(08:20) gp >  matsize(factor(18480))[1]
%8 = 5
(08:21) gp >  matsize(factor(6930))[1]
%9 = 5

Точно мне надо прогу корректировать.

[Yadryara]

wrest

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

Это обеспечивается через подбор паттерна и через КТО.

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

[wrest]

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

Надо же сначала понять что же считает ваша функция.

omega_upto(n,m,s)
n - целое число
m - максимальное количество различных простых множителей
s - пропускать несвободные от квадратов

s=1. Если количество различных простых множителей $\omega (n) \leq m $ то вернуть $\omega (n)$ (см. A001221), иначе вернуть ноль.
s=0. Если число не свободно от квадратов или $\omega (n) > m $, вернуть ноль. Иначе вернуть $\omega (n)$ (см. A001221)

"Не свободно от квадратов" означает что число делится на квадрат числа большего единицы.

-- 30.11.2025, 11:14 --

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

хочется поздравить, но рановато.

Поздавлять будем вас если справитесь с установкой

[Yadryara]

wrest
Вот, кстати, числа подлежащие проверке из рабочей программы:

17406126303170342587707303078752980565139499

198368257307306547367919233421959045941111127
67864683258213453905507434431649214364331717
51231361266412682617729208094195819174793817

27720211614413493095909609323615332724939333
329812967599172304533858794668689694030117289
75557627931954653991506295409632438822595241
6808281974011485429306085118517951541050278323
105613238378017502504471126492245231661721769
10590660848462310667809465739916813508300432947
37801287977854767404435927685604331380013443
3812637905446431840411407666370052862988155861
353676985662934308015900525637296183950663809
15885991272693466001714198609875220262450649421
563999690154797609528314743545865808134342583
4236264339384924267123786295966725403320173179
5957246727260049750642824478703207598418993533
3221384917659252615383854932127391438386667
9531594763616079601028519165925132157470389653
34366665814372019473692154915900963250298863
787735104431080958762687534373977864253751211

20716571327653129599025261239577452499526299

236095618293919953557257711858327013293248727
65178939724348484736720672535435868938469413
60974976936430280937523424105308320283475417

32992277036564937526323202136956850338056133
392539600658230234201599759681405293728048489
89927819730660751236038311968233158848518441
8103138899302038406018737896280437849100429523
125699661595821094386994272075264409847541289
12604882732247615298251370060880681098600668147
44990658175779709571390969878217779055088643
4537757783609141507370493221917045195496240533
420942280483222774338635734871711057096126209
18907324098371422947377055091321021647901002221
671265944320878921208652843478852839570449783
5041953092899046119300548024352272439440267259
7090246536889283605266395659245383117962875833
6041804627605173364805066468613752823338003
11344394459022853768426233054792612988740601333
26923921820393624702566116185576392521040943
937553261076268906481506864032447354441372011

Сначала одно число, для которого нужно 4 делителя, затем 3 числа, для которых нужно по 16 делителей. И наконец 17 чисел, для которых нужно по 8 делителей.

Затем цикл повторяется. И вот не разделится ни одно из этих чисел-кандидатов ни на одно простое меньше чем 67.

[wrest]

Вопрос теперь в какую тему писать про установку такого типа функции в pari/gp
Установка связана с
1. Сборкой приложений линукс из исходного кода.
2. Внесением изменений в исходный код и пересборка pari/gp, т.к. используется непубличный api движка факторизации pari/gp.
3. Донастройкой окружения ОС (доустановка необходимых пакетов/библиотек)

По второму пункту вроде подходит тема «интерактивный курс: введение в программирование на PARI/GP» но все-таки не вполне

По первому и третьему -- довольно косвенно подходит «Как установить Ubuntu под Win10 в WSL» но тоже не вполне ибо в части линукса действия универсальные, не WSL специфичные.

Видимо, нужна будет новая тема, Yadryara , Dmitriy40 что скажете?

В общем если будете готовы -- создавайте тему