Compute Prime Factors

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.

Factors.c

/********************************************************************************
* 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 [] ) */