text: Для чисел с небольшим простым делителем ситуация обратная — метод Лемана благодаря последовательным делениям на шаге один достаточно быстро выделит простой множитель. for a ← 2 {\displaystyle a\gets 2} to ⌊ n 1 / 3 ⌋ {\displaystyle \lfloor n^{1/3}\rfloor } do if a ⋮ n {\displaystyle a\vdots n} then return a {\displaystyle a} end if end for for k ← 1 {\displaystyle k\gets 1} to ⌊ n 1 / 3 ⌋ {\displaystyle \lfloor n^{1/3}\rfloor } do for d ← 0 {\displaystyle d\gets 0} to ⌊ n 1 / 6 4 k ⌋ + 1 {\displaystyle \left\lfloor {\frac {n^{1/6}}{4{\sqrt {k}}}}\right\rfloor +1} do if i s S q u a r e ( ( ⌊ 4 k n ⌋ + d ) 2 − 4 k n ) = t r u e {\displaystyle isSquare((\lfloor {\sqrt {4kn}}\rfloor +d)^{2}-4kn)=true} then A ← ⌊ 4 k n ⌋ + d {\displaystyle A\gets \lfloor {\sqrt {4kn}}\rfloor +d} B ← A 2 − 4 k n {\displaystyle B\gets {\sqrt {A^{2}-4kn}}} if 1 < g c d ( A + B , n ) < n {\displaystyle 1<gcd(A+B,n)<n} then return g c d ( A + B , n ) {\displaystyle gcd(A+B,n)} else if 1 < g c d ( A − B , n ) < n {\displaystyle 1<gcd(A-B,n)<n} then return g c d ( A − B , n ) {\displaystyle gcd(A-B,n)} end if end if end for end for Пояснения: a ⋮ n {\displaystyle a\vdots n} означает, что n {\displaystyle n} целочисленно делится на a {\displaystyle a} .