//$Header$
//********************************************************************************
//Copyright (c) 2003, 2018 David T. Ashley.
//********************************************************************************
//This file is part of "arith_large_cgi", a program that is designed to be
//invoked by a PHP script as part of serving a web page that performs
//calculations involving large integers.  (A secondary compiled program is
//used because a compiled program can perform certain  calculation-intensive
//tasks far more efficiently than a PHP script.)  This program is provided by
//David T. Ashley (dashley@gmail.com) under the MIT License (reproduced
//immediately below).
//********************************************************************************
//Permission is hereby granted, free of charge, to any person obtaining a copy
//of this software and associated documentation files (the "Software"), to deal
//in the Software without restriction, including without limitation the rights
//to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
//copies of the Software, and to permit persons to whom the Software is
//furnished to do so, subject to the following conditions:
//
//The above copyright notice and this permission notice shall be included in all
//copies or substantial portions of the Software.
//
//THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
//IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
//FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
//AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
//LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
//OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
//SOFTWARE.
//********************************************************************************
//
//Sieve of Eratosthenes Table Generation
//--------------------------------------
//This utility generates a sieve table used in trial division prime number factorization.
//The table is a table of differentials to be added to trial divisors.
//--------------------------------------------------------------------------------
#include <stdio.h>

#define NAMING_PREFIX    "SUBFUNC_PFACT_"
#define SIEVE_SIZE       (2310)     /* 2 * 3 * 5 * 7 * 11 */

unsigned int pfacts[] = {2, 3, 5, 7, 11};
unsigned int sieve_table_a[SIEVE_SIZE];
char *output_header[] = 
   {
   "//This file is an automatically-generated sieve table, generated by the",
   "//program \"sieve_gen.c\".",
   "//",
   NULL
   };
char *output_footer[] = 
   {
   "//",
   "//End of automatically-generated file.",
   NULL
   };


int main(int argc, char *argv[])
   {
   int i, j;
   unsigned p, q;
   unsigned current_factor;
   char **cptr;
    
   //Initialize the sieve table. */
   for (i=0; i < SIEVE_SIZE; i++)
      {
      sieve_table_a[i] = 1;
      }

   /* For each prime component, mark off all multiples. */
   for (i=0; i<sizeof(pfacts)/sizeof(pfacts[0]); i++)
      {
      current_factor = pfacts[i];

      p = 0;
      while (p < SIEVE_SIZE)
         {
	 sieve_table_a[p] = 0;
         p += current_factor;
	 }
      }

   //Output the header.
   cptr = output_header;
   while (*cptr)
      {
      printf("%s\n", *cptr);
      cptr++;
      }

   //Convert the table of multiples into a table of differentials.  Each non-zero
   //entry will be replaced by the distance to the next entry.
   for (i=0; i < SIEVE_SIZE; i++)
      {
      if (sieve_table_a[i])
         {
	 p = (i+1) % SIEVE_SIZE;
         while (sieve_table_a[p] == 0)
	    {
	    sieve_table_a[i]++;
            p = (p+1) % SIEVE_SIZE;
	    }
	 }
      }

   //Print out the table of differentials for reference.  Each entry will
   //be annotated with the prime factors that divide it.
   printf("//\n");
   printf("//For reference, below is the uncompressed table of differentials.  Each table\n");
   printf("//entry is annotated with the prime factors that divide it, if any.\n");
   printf("//\n");
   for (i=0; i < SIEVE_SIZE; i++)
      {
      printf("//   sieve_table[%5d]: %3d    (", i, sieve_table_a[i]);
      q = 0;
      for (j=0; j<sizeof(pfacts)/sizeof(pfacts[0]); j++)
	 {
	 if ((i % pfacts[j]) == 0)
	    {
	    printf("[%d]", pfacts[j]);
	    q = 1;
	    }
	 }
      if (!q)
	 printf("NONE");
      printf(")\n");
      }
   printf("//\n");

   //Now we compress the table and output the code proper.
   printf("#define  %sN_SIEVE_FACTORS     (%d)\n",  NAMING_PREFIX, sizeof(pfacts)/sizeof(pfacts[0]));
   printf("unsigned %ssieve_factors[] = {", NAMING_PREFIX);
   for (i=0; i<sizeof(pfacts)/sizeof(pfacts[0]); i++)
      {
      printf("%d", pfacts[i]);
      if (i != (sizeof(pfacts)/sizeof(pfacts[0]) - 1))
	 printf(","); 
      }
 
   printf("}\n");
   printf("//\n");
   q = 0;
   for (i=0; i < SIEVE_SIZE; i++)
      if (sieve_table_a[i])
         q++;
   printf("#define  %sN_SIEVE     (%u)\n",  NAMING_PREFIX, j);
   printf("unsigned %ssieve[] = {\n", NAMING_PREFIX);
   j = 0;
   for (i=0; i < SIEVE_SIZE; i++)
      {
      if (sieve_table_a[i])
         {
	 printf("   %3d", sieve_table_a[i]);
	 if (j==q)
	    printf(" ");
	 else
	    printf(",");
         printf(" /* [%5d] (was [%d]) */\n", j, i);
         j++;
	 }
      }
   printf("     };\n");

   //Output the footer.
   cptr = output_footer;
   while (*cptr)
      {
      printf("%s\n", *cptr);
      cptr++;
      }

   return(0);
   }

//******************************************************************************************************
//End of file SIEVE_GEN.C
//******************************************************************************************************