Edit Question - KnowledgeHub

Title Body

Up for consideration is the following function which can be used to (relatively quickly) factor a 64-bit unsigned integer into its prime factors. Note that the factoring is not probabalistic (i.e., it is exact). The algorithm is already fast enough to find that a number is prime or has few very large factors in a matter of several seconds, on modern hardware. The question: Can any improvements be made to the algorithm presented, while keeping it single-threaded, so that it can factor (arbitrary) very large unsigned 64-bit integers faster, preferably without using a probabalistic approach (e.g., Miller-Rabin) for determining primality? // system specific typedef for ulong should go here (or use boost::uint64_t) typedef unsigned __int64 ulong; typedef std::vector<ulong> ULongVector; // Caller needs to pass in an empty factors vector void GetFactors(ULongVector &factors, ulong num) { // Num has to be at least 2 to contain "prime" factors if (num<2) return; ulong workingNum=num; ulong nextOffset=2; // Will be used to skip multiples of 3, later // Factor out factors of 2 while (workingNum%2==0) { factors.push_back(2); workingNum/=2; } // Factor out factors of 3 while (workingNum%3==0) { factors.push_back(3); workingNum/=3; } // If all of the factors were 2s and 3s, done... if (workingNum==1) return; // sqrtNum is the (inclusive) upper bound of our search for factors ulong sqrtNum=(ulong) sqrt(double(workingNum+0.5)); // Factor out potential factors that are greate than or equal to 5 // The variable n represents the next potential factor to be tested for (ulong n=5;n<=sqrtNum;) { // Is n a factor of the current working number? if (workingNum%n==0) { // n is a factor, so add it to the list of factors factors.push_back(n); // Divide current working number by n, to get remaining number to factor workingNum/=n; // Check

Tags (comma-separated) Cancel