//-----------------------------------------------------------------------------
// Name: prime_test.c
// Uses: Check the numbers on the command line to see if they are prime.
// Date: 02/02/2010
// Author: Andrew Que (http://www.DrQue.net/)
// Revisions:
//  1.0 - 02/02/2010- QUE - Creation.
//
// Build instructions:
//   This software was designed to compile and run in with strict C99 
// compliance.
//
//   gcc -Wall -std=c99 -pedantic -O3 prime_test.c -o prime_test
//
//   Verified on:
//     Ubuntu desktop 9.10 (x86_64), gcc 4.4.1
//     Ubuntu server 9.04 (i686), gcc 4.3.3
//     SunOS Blue-Solaris 5.11; gcc 3.4.3
//     NetBSD 4.0.1, gcc 4.1.2--crashes shortly after printing banner.
//     Cygwin 1.5.25; gcc 3.4.4
//
//                     (C) Copyright 2010 by Andrew Que
//                        Released as public domain.
//-----------------------------------------------------------------------------
#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>

// There happen to be 6542 primes between 2 and 65536.
enum { NUMBER_OF_LOOKUP_PRIMES = 6542 };
static unsigned PrimeNumbers[ NUMBER_OF_LOOKUP_PRIMES ];

//-----------------------------------------------------------------------------
// FUNCTION INFORMATION:
//   Build a lookup table (PrimeNumbers) of all prime numbers between 2 and
// 65536 (or the square root of 2^32).  This function doesn't take long
// despite having to check 2^16-2 values.
//-----------------------------------------------------------------------------
static void GeneratePrimeNumberLookup()
{
  unsigned Index;
  unsigned PrimeNumberCount = 0;

  // First prime number in our list is 2.  We can get all the rest
  // knowing this.
  PrimeNumbers[ PrimeNumberCount++ ] = 2;

  // Get all remaining prime numbers between 3 and 2^16.
  for ( Index = 3; Index < 0x10000ul; ++Index )
  {
    // Assume the number is prime until it is determined to be otherwise.
    bool IsPrime = true;

    // First check: is the number even?
    if ( 0 == ( Index & 1 ) )
    {
      // No even numbers (except 2) are prime.
      IsPrime = false;
    }
    else
    {
      // Check to see if this number is prime...
      unsigned SubIndex = 0;
      while ( ( SubIndex < PrimeNumberCount )
           && ( IsPrime ) )
      {
        // Does it divide evenly by this prime number?
        if ( 0 == ( Index % PrimeNumbers[ SubIndex ] ) )
        {
          // If so, this number isn't prime.
          IsPrime = false;
          break; // <- We can stop checking.
        }

        ++SubIndex;
      }
    }

    // If this number doesn't divide evenly, it is prime...
    if ( IsPrime )
      // Add numbe to our prime list.
      PrimeNumbers[ PrimeNumberCount++ ] = Index;
  }

} // GeneratePrimeNumberLookup

//-----------------------------------------------------------------------------
// FUNCTION USAGE:
//   Return the integer square root of some unsigned 32-bit value.  This
// function uses a power-of-two bit trick such that the function will always
// have a value in 16 iterations.
//
// INPUT:
//    Argument - The number of which to find the square root.
//
// OUTPUT:
//    Integer portion of the square root of "Argument".
//-----------------------------------------------------------------------------
static inline uint16_t SquareRoot( uint32_t Argument )
{
  uint32_t Test;
  uint16_t Root    = 0;
  uint16_t BitMask = ( 1U << 15 );

  // 16 laps.
  while ( BitMask )
  {
    Test = Root + BitMask;

    // Argument >= Test^2?
    if ( Argument >= ( Test * Test ) )
      Root = Test; // <- Use result.

    BitMask >>= 1;
  }

  return Root;

} // SquareRoot

//-----------------------------------------------------------------------------
// FUNCTION USAGE:
//   Test to see if a number is a prime number.  Works on a 32-bit unsigned
// value by dividing it by all prime number up to the square root of the
// number.  This works because because of the nature of prime numbers.  A
// number (call it x) is prime if there are no two number (call them a and b)
// such that a * b = x.  All non-prime numbers can be expressed as the sum of
// two or more prime numbers.  For example, 125 can be made from 5 * 25, but
// 25 can be made from 5 * 5.  So 5 * 5 * 5 = 125, and represents the most
// factored version of 125.  This is true of any number.  Since it takes at
// least two prime numbers to create a factor, we only need to check the primes
// up to x^1/2 (or the square root) of the number.  This is because the if
// x = a * a, then x^1/2 = a.  If x = a * b, and b is greater a, then a must
// be less then x^1/2. Thus, we only need to check primes up to x^1/2.
//   Since the input is a 32-bit number, maximum number that can be represented
// is 2^32-1.  (2^32)^1/2 = 2^16.  So we need to check all primes up to 2^16.
// To do this, we keep a lookup table of all primes in this range.
//
// INPUT:
//   Number - A unsigned 32-bit value to test.
//
// OUTPUT:
//   Returns true if Number is prime, false if not.
//-----------------------------------------------------------------------------
static inline bool IsPrime( uint32_t Number )
{
  // Have we not yet build the prime number table?
  if ( 0 == PrimeNumbers[ 0 ] )
    GeneratePrimeNumberLookup();

  // Assume the number is prime until it is determined to be otherwise.
  bool IsPrime = true;

  // Is number even (and not the number 2)?
  if ( ( 0 == ( Number & 1 ) )
    && ( 2 != Number ) )
  {
    // No even numbers (except 2) are prime.
    IsPrime = false;
  }
  else
  {
    // We only need to check up to the square root of the number.
    uint16_t Root = SquareRoot( Number );
    unsigned Index = 1; // <- Start with 3.

    // While we still have prime numbers to test, the number is less
    // then the squre root of the number, and nothing so far has divided
    // evenly...
    while ( ( Index < NUMBER_OF_LOOKUP_PRIMES )
         && ( PrimeNumbers[ Index ] <= Root )
         && ( IsPrime ) )
    {
      // Does this prime divide into the number?
      if ( 0 == ( Number % PrimeNumbers[ Index ] ) )
        // Then the number is not prime.
        IsPrime = false;

      ++Index;
    }
  }

  // Return the results.
  return IsPrime;

} // IsPrime

//-----------------------------------------------------------------------------
// FUNCTION USAGE:
//   Program main function.  This program will take a list of numbers from the
// command line and test to see if they are prime numbers or not.
//
// INPUT:
//   Parameters from the command line.  Expects the parameters to be a list
// of one or more numbers between 0 and 2^32-1.
//
// OUTPUT:
//   This function (and program as a whole) returns 0 if successful, -1 if 
// there were no parameters..
//-----------------------------------------------------------------------------
int main( int ParameterCount, char const * const * Parameters )
{
  int Result = 0;

  // Make sure there is at least 1 parameter.
  if ( ParameterCount < 2 )
  {
    // Warn about lack of parameters.
    printf( "You must specify some number to test.\n" );
    Result = -1;
  }
  else
  {
    // For all parameters...
    unsigned Index;
    for ( Index = 1; Index < ParameterCount; ++Index )
    {
      unsigned long Number;
      int Results = sscanf( Parameters[ Index ], "%lu", &Number );

      // Problems?
      if ( 1 != Results )
      {
        // Print a message about this parameter.
        printf( 
          "Skipping parameter %i, '%s' as it is not an number.\n", 
          Index, 
          Parameters[ Index ] );
      }
      else
      {
        // Test number.
        bool Result = IsPrime( Number );

        // Display results.
        char const * const Results[ 2 ] = { "not ", "" };
        printf( "%lu is %sprime.\n", Number, Results[ Result ] );
      }
    }
  }

  return Result;

} // main

//--------------------------------------=--------------------------------------