bridge/class-master/depend/pari/src/basemath/ifactor1.c
/* Factor until the unfactored part is smaller than limit. Return the
 * factored part. Hence factorback(output) may be smaller than n */
Factor until the unfactored part is smaller than limit. Return the
factored part. Hence factorback(output) may be smaller than n
Factor until the unfactored part is smaller than limit . Return the factored part . Hence factorback ( output ) may be smaller than n
GEN
Z_factor_until(GEN n, GEN limit)
{
  pari_sp av2, av = avma;
  ulong B = tridiv_bound(n);
  GEN q, part, F = ifactor(n, B, decomp_default_hint);
  GEN P = gel(F,1), E = gel(F,2);
  long l = lg(P);
  av2 = avma;
  q = gel(P,l-1);
  if (abscmpiu(q, B) <= 0 || cmpii(q, sqru(B)) < 0 || ifac_isprime(q))
  {
    avma = av2; return F;
  }
  setlg(E,l-1);
  setlg(P,l-1);
  if (cmpii(q, limit) > 0)
  { 
    long l2 = expi(q)+1;
    GEN  P2 = coltrunc_init(l2);
    GEN  E2 = coltrunc_init(l2);
    GEN  F2 = mkmat2(P2,E2);
    part = ifac_start(icopy(q), 0); 
    for(;;)
    {
      long e;
      GEN p;
      if (!ifac_next(&part,&p,&e)) break;
      vectrunc_append(P2, p);
      vectrunc_append(E2, utoipos(e));
      q = diviiexact(q, powiu(p, e));
      if (cmpii(q, limit) <= 0) break;
    }
    F2 = sort_factor(F2, (void*)&abscmpii, cmp_nodata);
    F = merge_factor(F, F2, (void*)&abscmpii, cmp_nodata);
  }
  return gerepilecopy(av, F);
}
GEN Z_factor_until ( GEN n , GEN limit ) { pari_sp av2 , av = avma ; ulong B = tridiv_bound ( n ) ; GEN q , part , F = ifactor ( n , B , decomp_default_hint ) ; GEN P = gel ( F , 1 ) , E = gel ( F , 2 ) ; long l = lg ( P ) ; av2 = avma ; q = gel ( P , l - 1 ) ; if ( abscmpiu ( q , B ) <= 0 || cmpii ( q , sqru ( B ) ) < 0 || ifac_isprime ( q ) ) { avma = av2 ; return F ; } setlg ( E , l - 1 ) ; setlg ( P , l - 1 ) ; if ( cmpii ( q , limit ) > 0 ) { long l2 = expi ( q ) + 1 ; GEN P2 = coltrunc_init ( l2 ) ; GEN E2 = coltrunc_init ( l2 ) ; GEN F2 = mkmat2 ( P2 , E2 ) ; part = ifac_start ( icopy ( q ) , 0 ) ; for ( ; ; ) { long e ; GEN p ; if ( ! ifac_next ( & part , & p , & e ) ) break ; vectrunc_append ( P2 , p ) ; vectrunc_append ( E2 , utoipos ( e ) ) ; q = diviiexact ( q , powiu ( p , e ) ) ; if ( cmpii ( q , limit ) <= 0 ) break ; } F2 = sort_factor ( F2 , ( void * ) & abscmpii , cmp_nodata ) ; F = merge_factor ( F , F2 , ( void * ) & abscmpii , cmp_nodata ) ; } return gerepilecopy ( av , F ) ; }
Factor until the unfactored part is smaller than limit.
Factor until the unfactored part is smaller than limit .
/* q = composite unfactored part, remove from P/E */ /* factor further */ /* ifac_next would destroy q */