1/* 2 * smallfactors - find the factors of a number < 2^32 3 * 4 * Copyright (C) 2013 Christoph Zurnieden 5 * 6 * Calc is open software; you can redistribute it and/or modify it under 7 * the terms of the version 2.1 of the GNU Lesser General Public License 8 * as published by the Free Software Foundation. 9 * 10 * Calc is distributed in the hope that it will be useful, but WITHOUT 11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 12 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General 13 * Public License for more details. 14 * 15 * A copy of version 2.1 of the GNU Lesser General Public License is 16 * distributed with calc under the filename COPYING-LGPL. You should have 17 * received a copy with calc; if not, write to Free Software Foundation, Inc. 18 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. 19 */ 20 21 22static resource_debug_level; 23resource_debug_level = config("resource_debug", 0); 24 25 26define smallfactors(x0) 27{ 28 local d q x flist tuple w; 29 30 if (x >= (2 ^ 32) - 1) 31 return newerror("smallfactors: number must be < 2^32 -1"); 32 33 tuple = mat[2]; 34 flist = list(); 35 x = x0; 36 d = 2; 37 q = 0; 38 tuple[0] = d; 39 if (x < 2) 40 return 0; 41 do { 42 q = x // d; 43 while (x == (q * d)) { 44 tuple[0] = d; 45 tuple[1]++; 46 x = floor(q); 47 q = x // d; 48 } 49 d = nextprime(d); 50 if (tuple[1] > 0) 51 append(flist, tuple); 52 tuple = mat[2]; 53 } while (d <= x); 54 return flist; 55} 56 57define printsmallfactors(flist) 58{ 59 local k; 60 for (k = 0; k < size(flist); k++) { 61 print flist[k][0]:"^":flist[k][1]; 62 } 63} 64 65 66config("resource_debug", resource_debug_level),; 67if (config("resource_debug") & 3) { 68 print "smallfactors(x0)"; 69 print "printsmallfactors(flist)"; 70 71} 72