Changeset be8dbb in git
 Timestamp:
 Jun 24, 2010, 1:53:51 PM (14 years ago)
 Branches:
 (u'fiekerDuVal', '117eb8c30fc9e991c4decca4832b1d19036c4c65')(u'spielwiese', 'b52fc4b2495505785981d640dcf7eb3e456778ef')
 Children:
 5402320461972a7e82662b640cf0e4c3d9c0cf02
 Parents:
 672bbc79fdc4b3d9f36f868b04fbd9789b639b71
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

Singular/LIB/general.lib
r672bbc rbe8dbb 27 27 which(command); search for command and return absolute path, if found 28 28 primecoeffs(J[,q]); primefactors <= min(p,32003) of coeffs of J 29 primefactors(n[,p]); primefactors <= min(p,32003) of n30 29 timeStd(i,d) std(i) if the standard basis computation finished 31 30 after d1 seconds and i otherwhise … … 1170 1169 l; 1171 1170 } 1172 ///////////////////////////////////////////////////////////////////////////////1173 proc primefactors (n, list #)1174 "USAGE: primefactors(n [,p]); n = int or number, p = integer1175 COMPUTE: primefactors <= min(p,32003) of n (default p = 32003)1176 RETURN: a list, say l,1177 l[1] : primefactors <= min(p,32003) of n1178 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 procedure1182 finds primefactors <= min(p,32003) but n may be as larger as1183 2147483647 (max. integer representation)1184 WARNING: the procedure works for small integers only, just by testing all1185 primes (not to be considerd as serious prime factorization!)1186 EXAMPLE: example primefactors; shows an example1187 "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 else1197 {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 representation1212 {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 possible1223 if (denominator(m)!=1) { break; }1224 n=m;1225 }1226 if( jj>1 )1227 {1228 w1 = w1,v[ii]; //primes1229 w2 = w2,jj1; //powers1230 }1231 if( n <= 2147483647 ) { break; }1232 }1233 }1234 1235 if( n > 2147483647 ) //n is still too big1236 {1237 if( size(w1) >1 ) //at least 1 primefactor was found1238 {1239 w1 = w1[2..size(w1)];1240 w2 = w2[2..size(w2)];1241 }1242 else //no primefactor was found1243 {1244 w1 = 1; w2 = 1;1245 }1246 l = w1,w2,n;1247 return(l);1248 }1249 1250 if( n <= 2147483647 ) //n is in inter range1251 {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 found1269 {1270 w1 = w1[2..size(w1)];1271 w2 = w2[2..size(w2)];1272 }1273 else //no primefactor was found1274 {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 Singular1281 { //case n is a prime1282 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 else1291 {1292 w3=n;1293 if( size(w1) >1 ) //at least 1 primefactor was found1294 {1295 w1 = w1[2..size(w1)];1296 w2 = w2[2..size(w2)];1297 }1298 else //no primefactor was found1299 {1300 w1 = 1; w2 = 1;1301 }1302 l=w1,w2,w3;1303 return(l);1304 }1305 }1306 else1307 {1308 if ( p >= n)1309 {1310 v = primes(q,n div 2 + 1);1311 }1312 else1313 {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]; //primes1328 w2 = w2,z; //multiplicities1329 }1330 }1331 }1332 // case:at least 1 primefactor was found 1333 if( size(w1) >1 ) //at least 1 primefactor was found1334 {1335 w1 = w1[2..size(w1)];1336 w2 = w2[2..size(w2)];1337 }1338 else //no primefactor was found1339 {1340 w1 = 1; w2 = 1;1341 }1342 w3 = n;1343 l = w1,w2,w3;1344 return(l);1345 }1346 example1347 { "EXAMPLE:"; echo = 2;1348 primefactors(7*8*121);1349 ring r = 0,x,dp;1350 primefactors(123456789100);1351 }1352 1171 1353 1172 /////////////////////////////////////////////////////////////////////////////// … … 1377 1196 } 1378 1197 q=#[1]; 1198 if (q > 32003) { q = 32003; } 1379 1199 } 1380 1200
Note: See TracChangeset
for help on using the changeset viewer.