The Prime Factors Computation works for all positive non-zero integers that will fit into an unsigned __int64 value - i.e. 1 to 18,446,744,073,709,551,615 (i.e. 18.447 Quintillion). Obviously, I have not exhaustively confirmed that this code works for all of these numbers. I confirmed a representative sample by computing the factors and multiplying them back together using Excel. So far, everything I have tried has worked. Use this code at your own discression.

If you are curious, I woke up one morning from dreaming about this manner of factoring integers into their prime factors. I haven't got a clue about what caused me to dream about this and I don't remember what I ate before going to bed. At any rate, this code is the result of that dream.

/******************************************************************************** * Copyright (c) 2010 Cass Tyler, PO Box 1026, Willard, NM 87063, (505) 384-5342 * ********************************************************************************/ #define UNREFERENCED_PARAMETER(P) ( P ) #include <STDLIB.H> #pragma warning ( disable : 4514 ) /* Disable the ": warning C4514: '<function>' : unreferenced inline function has been removed" warnings (don't re-enable) */ #include <MATH.H> #include <STDIO.H> int main ( int argc, char * argv [],char * envp [] ) { unsigned __int64 ulNumber = ( unsigned __int64 ) _atoi64 ( argv [ 1 ] ? argv [ 1 ] : "0" ); UNREFERENCED_PARAMETER ( envp ); /* Check the Argument */ if ( argc < 2 || argv [ 1 ] [ 0 ] == '-' || argv [ 1 ] [ 0 ] == '/' || ulNumber < 1UI64 ) { /* 18446744073709551566 = 1 * 2 * 9223372036854775783 exits in a few seconds while 18446744073709551557 takes forever */ fprintf ( stdout, "Usage: Factors <positive integer> - i.e. \"Factors %I64u\"\n", 0xFFFFFFFFFFFFFFFFUI64 ); return 1; } /* Decode the Argument */ /* 1 is Always a Factor */ printf ( "%I64u = 1", ulNumber ); if ( ulNumber == 1LU ) return 0; /* Find the Even Factors */ while ( ( ulNumber & 1LU ) == 0 ) { printf ( " * 2" ); ulNumber >>= 1; } /* Find the Odd Factors */ for (;;) { unsigned __int64 ullStart = 3UI64; unsigned __int64 ullTry = 0UI64; /************************************************************ * Determine When to Stop Looking * * * * For any integer that is the product of two integers, the * * lesser of the two integers will be less than or equal to * * the square root of the number. If we haven't found a * * prime factor by now, the number is garanteed to be a * * prime factor. * ************************************************************/ unsigned __int64 ulSqrt = ( unsigned __int64 ) sqrt ( ( double ) ( signed __int64 ) ulNumber ); /* 1 00 00 00 00 Hex or 4294967296 Decimal is the Maximum Square Root for a 64 Bit Number */ if ( ulSqrt > 0x100000000UI64 ) ulSqrt = 0x100000000UI64; /* Check Only the Odd Numbers */ for ( ullTry = ullStart; ullTry <= ulSqrt; ullTry += 2UI64 ) { if ( ulNumber % ullTry == 0LU ) { printf ( " * %I64u", ullTry ); ulNumber /= ullTry; ullStart = ullTry; /* The Smaller Factors have already been Found */ break; } } /* Check for No Factors Found */ if ( ullTry >= ulSqrt ) { if ( ulNumber != 1 ) printf ( " * %I64u", ulNumber ); break; } } printf ( "\n" ); return 0; } /* int main ( int argc, char * argv [],char * envp [] ) */

Please send any comments, suggestions or bug reports to Cass Tyler