Changeset be8dbb in git


Ignore:
Timestamp:
Jun 24, 2010, 1:53:51 PM (14 years ago)
Author:
Frank Seelisch <seelisch@…>
Branches:
(u'fieker-DuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', 'b52fc4b2495505785981d640dcf7eb3e456778ef')
Children:
5402320461972a7e82662b640cf0e4c3d9c0cf02
Parents:
672bbc79fdc4b3d9f36f868b04fbd9789b639b71
Message:
removed primefactors from general.lib (now in the kernel with same syntax)

git-svn-id: file:///usr/local/Singular/svn/trunk@12904 2c84dea3-7e68-4137-9b89-c4e89433aadc
File:
1 edited

Legend:

Unmodified
Added
Removed
  • Singular/LIB/general.lib

    r672bbc rbe8dbb  
    2727 which(command);        search for command and return absolute path, if found
    2828 primecoeffs(J[,q]);    primefactors <= min(p,32003) of coeffs of J
    29  primefactors(n[,p]);  primefactors <= min(p,32003) of n
    3029 timeStd(i,d)           std(i) if the standard basis computation finished
    3130                        after d-1 seconds and i otherwhise
     
    11701169   l;
    11711170}
    1172 ///////////////////////////////////////////////////////////////////////////////
    1173 proc primefactors (n, list #)
    1174 "USAGE:   primefactors(n [,p]); n = int or number, p = integer
    1175 COMPUTE: primefactors <= min(p,32003) of n (default p = 32003)
    1176 RETURN:  a list, say l,
    1177          l[1] : primefactors <= min(p,32003) of n
    1178          l[2] : l[2][i] = multiplicity of l[1][i]
    1179          l[3] : remaining factor ( n=product{ (l[1][i]^l[2][i])*l[3]} )
    1180                 type(l[3])=typeof(n)
    1181 NOTE:    If n is a long integer (of type number) then the procedure
    1182          finds primefactors <= min(p,32003) but n may be as larger as
    1183          2147483647 (max. integer representation)
    1184 WARNING: the procedure works for small integers only, just by testing all
    1185          primes (not to be considerd as serious prime factorization!)
    1186 EXAMPLE: example primefactors; shows an example
    1187 "
    1188 {
    1189    int ii,jj,z,p,num,w3,q;
    1190    intvec w1,w2,v;
    1191    list l;
    1192    if (size(#) == 0)
    1193    {
    1194       p=32003;
    1195    }
    1196    else
    1197    {
    1198      if( typeof(#[1]) != "int")
    1199      {
    1200        ERROR("2nd parameter must be of type int"+newline);
    1201      }
    1202      p=#[1];
    1203    }
    1204    if( n<0) { n=-n;};
    1205 
    1206 // ----------------- case: 1st parameter is a number --------------------
    1207    if (typeof(n) =="number")
    1208    {
    1209      kill w3;
    1210      number w3;
    1211      if( n > 2147483647 )           //2147483647 max. integer representation
    1212      {
    1213         v = primes(2,p);
    1214         number m;
    1215         for( ii=1; ii<=size(v); ii++)
    1216         {
    1217           jj=0;
    1218           while(1)
    1219           {
    1220             q  = v[ii];
    1221             jj = jj+1;
    1222             m  = n/q;                  //divide n as often as possible
    1223             if (denominator(m)!=1) { break;  }
    1224             n=m;
    1225           }
    1226           if( jj>1 )
    1227           {
    1228              w1 = w1,v[ii];          //primes
    1229              w2 = w2,jj-1;           //powers
    1230           }
    1231           if( n <= 2147483647 ) { break;  }
    1232         }
    1233      }
    1234 
    1235      if( n >  2147483647 )            //n is still too big
    1236      {
    1237        if( size(w1) >1 )               //at least 1 primefactor was found
    1238        {
    1239          w1 = w1[2..size(w1)];
    1240          w2 = w2[2..size(w2)];
    1241        }
    1242        else                           //no primefactor was found
    1243        {
    1244          w1 = 1; w2 = 1;
    1245        }
    1246        l  = w1,w2,n;
    1247        return(l);
    1248      }
    1249 
    1250      if( n <= 2147483647 )          //n is in inter range
    1251      {
    1252        num = int(n);
    1253        kill n;
    1254        int n = num;
    1255      }
    1256    }
    1257 
    1258 // --------------------------- trivial cases --------------------
    1259    if( n==0 )
    1260    {
    1261      w1=1; w2=1; w3=0; l=w1,w2,w3;
    1262      return(l);
    1263    }
    1264 
    1265    if( n==1 )
    1266    {
    1267        w3=1;
    1268        if( size(w1) >1 )               //at least 1 primefactor was found
    1269        {
    1270          w1 = w1[2..size(w1)];
    1271          w2 = w2[2..size(w2)];
    1272        }
    1273        else                           //no primefactor was found
    1274        {
    1275          w1 = 1; w2 = 1;
    1276        }
    1277       l=w1,w2,w3;
    1278       return(l);
    1279    }
    1280    if ( prime(n)==n )         //note: prime(n) <= 32003 in Singular
    1281    {                          //case n is a prime
    1282       if (p > n)
    1283       {
    1284         w1=w1,n; w2=w2,1; w3=1;
    1285         w1 = w1[2..size(w1)];
    1286         w2 = w2[2..size(w2)];
    1287         l=w1,w2,w3;
    1288         return(l);
    1289       }
    1290       else
    1291       {
    1292         w3=n;
    1293         if( size(w1) >1 )               //at least 1 primefactor was found
    1294         {
    1295            w1 = w1[2..size(w1)];
    1296            w2 = w2[2..size(w2)];
    1297          }
    1298          else                           //no primefactor was found
    1299          {
    1300            w1 = 1; w2 = 1;
    1301          }
    1302          l=w1,w2,w3;
    1303         return(l);
    1304       }
    1305    }
    1306    else
    1307    {
    1308       if ( p >= n)
    1309       {
    1310          v = primes(q,n div 2 + 1);
    1311       }
    1312       else
    1313       {
    1314          v = primes(q,p);
    1315       }
    1316 //------------- search for primfactors <= last entry of v ------------
    1317       for(ii=1; ii<=size(v); ii++)
    1318       {
    1319          z=0;
    1320          while( (n mod v[ii]) == 0 )
    1321          {
    1322             z=z+1;
    1323             n = n div v[ii];
    1324          }
    1325          if (z!=0)
    1326          {
    1327             w1 = w1,v[ii];        //primes
    1328             w2 = w2,z;            //multiplicities
    1329          }
    1330       }
    1331    }
    1332 //--------------- case:at least 1 primefactor was found ---------------
    1333    if( size(w1) >1 )               //at least 1 primefactor was found
    1334    {
    1335       w1 = w1[2..size(w1)];
    1336       w2 = w2[2..size(w2)];
    1337    }
    1338    else                           //no primefactor was found
    1339    {
    1340      w1 = 1; w2 = 1;
    1341    }
    1342    w3 = n;
    1343    l  = w1,w2,w3;
    1344    return(l);
    1345 }
    1346 example
    1347 { "EXAMPLE:"; echo = 2;
    1348    primefactors(7*8*121);
    1349    ring r = 0,x,dp;
    1350    primefactors(123456789100);
    1351 }
    13521171
    13531172///////////////////////////////////////////////////////////////////////////////
     
    13771196     }
    13781197     q=#[1];
     1198     if (q > 32003) { q = 32003; }
    13791199   }
    13801200
Note: See TracChangeset for help on using the changeset viewer.