20180707_cgi_web_tools_aux_exe/dtats_cgi_aux_arith_large/sieve_gen.c

//$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
//******************************************************************************************************
1	dashley	172	//$Header$
2	dashley	175	//********************************************************************************
3			//Copyright (c) 2003, 2018 David T. Ashley.
4			//********************************************************************************
5			//This file is part of "arith_large_cgi", a program that is designed to be
6			//invoked by a PHP script as part of serving a web page that performs
7			//calculations involving large integers. (A secondary compiled program is
8			//used because a compiled program can perform certain calculation-intensive
9			//tasks far more efficiently than a PHP script.) This program is provided by
10			//David T. Ashley (dashley@gmail.com) under the MIT License (reproduced
11			//immediately below).
12			//********************************************************************************
13			//Permission is hereby granted, free of charge, to any person obtaining a copy
14			//of this software and associated documentation files (the "Software"), to deal
15			//in the Software without restriction, including without limitation the rights
16			//to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
17			//copies of the Software, and to permit persons to whom the Software is
18			//furnished to do so, subject to the following conditions:
19	dashley	172	//
20	dashley	175	//The above copyright notice and this permission notice shall be included in all
21			//copies or substantial portions of the Software.
22			//
23			//THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
24			//IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
25			//FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
26			//AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
27			//LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
28			//OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
29			//SOFTWARE.
30			//********************************************************************************
31			//
32	dashley	172	//Sieve of Eratosthenes Table Generation
33			//--------------------------------------
34			//This utility generates a sieve table used in trial division prime number factorization.
35			//The table is a table of differentials to be added to trial divisors.
36			//--------------------------------------------------------------------------------
37			#include <stdio.h>
38
39			#define NAMING_PREFIX "SUBFUNC_PFACT_"
40			#define SIEVE_SIZE (2310) /* 2 * 3 * 5 * 7 * 11 */
41
42			unsigned int pfacts[] = {2, 3, 5, 7, 11};
43			unsigned int sieve_table_a[SIEVE_SIZE];
44	dashley	207	char *output_header[] =
45	dashley	172	{
46			"//This file is an automatically-generated sieve table, generated by the",
47			"//program \"sieve_gen.c\".",
48			"//",
49			NULL
50			};
51	dashley	207	char *output_footer[] =
52	dashley	172	{
53			"//",
54			"//End of automatically-generated file.",
55			NULL
56			};
57
58
59			int main(int argc, char *argv[])
60			{
61			int i, j;
62			unsigned p, q;
63			unsigned current_factor;
64			char **cptr;
65	dashley	207
66	dashley	172	//Initialize the sieve table. */
67			for (i=0; i < SIEVE_SIZE; i++)
68			{
69			sieve_table_a[i] = 1;
70			}
71
72			/* For each prime component, mark off all multiples. */
73			for (i=0; i<sizeof(pfacts)/sizeof(pfacts[0]); i++)
74			{
75			current_factor = pfacts[i];
76
77			p = 0;
78			while (p < SIEVE_SIZE)
79			{
80	dashley	207	sieve_table_a[p] = 0;
81	dashley	172	p += current_factor;
82	dashley	207	}
83	dashley	172	}
84
85			//Output the header.
86			cptr = output_header;
87			while (*cptr)
88			{
89			printf("%s\n", *cptr);
90			cptr++;
91			}
92
93			//Convert the table of multiples into a table of differentials. Each non-zero
94			//entry will be replaced by the distance to the next entry.
95			for (i=0; i < SIEVE_SIZE; i++)
96			{
97			if (sieve_table_a[i])
98			{
99	dashley	207	p = (i+1) % SIEVE_SIZE;
100	dashley	172	while (sieve_table_a[p] == 0)
101	dashley	207	{
102			sieve_table_a[i]++;
103	dashley	172	p = (p+1) % SIEVE_SIZE;
104	dashley	207	}
105			}
106	dashley	172	}
107
108			//Print out the table of differentials for reference. Each entry will
109			//be annotated with the prime factors that divide it.
110			printf("//\n");
111			printf("//For reference, below is the uncompressed table of differentials. Each table\n");
112			printf("//entry is annotated with the prime factors that divide it, if any.\n");
113			printf("//\n");
114			for (i=0; i < SIEVE_SIZE; i++)
115			{
116			printf("// sieve_table[%5d]: %3d (", i, sieve_table_a[i]);
117			q = 0;
118			for (j=0; j<sizeof(pfacts)/sizeof(pfacts[0]); j++)
119	dashley	207	{
120			if ((i % pfacts[j]) == 0)
121			{
122			printf("[%d]", pfacts[j]);
123			q = 1;
124			}
125			}
126	dashley	172	if (!q)
127	dashley	207	printf("NONE");
128	dashley	172	printf(")\n");
129			}
130			printf("//\n");
131
132			//Now we compress the table and output the code proper.
133			printf("#define %sN_SIEVE_FACTORS (%d)\n", NAMING_PREFIX, sizeof(pfacts)/sizeof(pfacts[0]));
134			printf("unsigned %ssieve_factors[] = {", NAMING_PREFIX);
135			for (i=0; i<sizeof(pfacts)/sizeof(pfacts[0]); i++)
136			{
137			printf("%d", pfacts[i]);
138			if (i != (sizeof(pfacts)/sizeof(pfacts[0]) - 1))
139	dashley	207	printf(",");
140	dashley	172	}
141	dashley	207
142	dashley	172	printf("}\n");
143			printf("//\n");
144			q = 0;
145			for (i=0; i < SIEVE_SIZE; i++)
146			if (sieve_table_a[i])
147			q++;
148			printf("#define %sN_SIEVE (%u)\n", NAMING_PREFIX, j);
149			printf("unsigned %ssieve[] = {\n", NAMING_PREFIX);
150			j = 0;
151			for (i=0; i < SIEVE_SIZE; i++)
152			{
153			if (sieve_table_a[i])
154			{
155	dashley	207	printf(" %3d", sieve_table_a[i]);
156			if (j==q)
157			printf(" ");
158			else
159			printf(",");
160	dashley	172	printf(" /* [%5d] (was [%d]) */\n", j, i);
161			j++;
162	dashley	207	}
163	dashley	172	}
164			printf(" };\n");
165
166			//Output the footer.
167			cptr = output_footer;
168			while (*cptr)
169			{
170			printf("%s\n", *cptr);
171			cptr++;
172			}
173
174			return(0);
175			}
176
177			//******************************************************************************************************
178	dashley	175	//End of file SIEVE_GEN.C
179	dashley	172	//******************************************************************************************************