2018/20180707_cgi_web_tools_aux_exe/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	//$Header$
2	//********************************************************************************
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	//
20	//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	//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	char *output_header[] =
45	{
46	"//This file is an automatically-generated sieve table, generated by the",
47	"//program \"sieve_gen.c\".",
48	"//",
49	NULL
50	};
51	char *output_footer[] =
52	{
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
66	//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	sieve_table_a[p] = 0;
81	p += current_factor;
82	}
83	}
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	p = (i+1) % SIEVE_SIZE;
100	while (sieve_table_a[p] == 0)
101	{
102	sieve_table_a[i]++;
103	p = (p+1) % SIEVE_SIZE;
104	}
105	}
106	}
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	{
120	if ((i % pfacts[j]) == 0)
121	{
122	printf("[%d]", pfacts[j]);
123	q = 1;
124	}
125	}
126	if (!q)
127	printf("NONE");
128	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	printf(",");
140	}
141
142	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	printf(" %3d", sieve_table_a[i]);
156	if (j==q)
157	printf(" ");
158	else
159	printf(",");
160	printf(" /* [%5d] (was [%d]) */\n", j, i);
161	j++;
162	}
163	}
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	//End of file SIEVE_GEN.C
179	//******************************************************************************************************