/home/toolbox/public_html/solutions/101/10168/b.c
1 #include <stdio.h>
2 #include <string.h>
3 #include <sys/types.h>
4 #include <sys/stat.h>
5 #include <fcntl.h>
6 #include <stdint.h>
7 #include <math.h>
8 #include <stdlib.h>
9
10 #define TRUE (1 == 1)
11 #define FALSE (1 != 1)
12
13 #define DEBUG if (FALSE)
14
15
16 /*
17 * Author: Isaac Traxler
18 * Date: 2020-09-01
19 * Purpose: fun
20 * Problem: 10168
21 */
22
23 /*
24 * This template reads lines of data at a time until end of file.
25 */
26
27 #define MAX_LINE 257
28 #define MAX_NUM 10000001
29 #define MAX_PRIMES 664581
30
31 char line[MAX_LINE];
32 unsigned int flags[MAX_NUM+3][4];
33 unsigned int primes[MAX_PRIMES];
34 int numPrimes;
35 int num;
36
37
38 void init()
39 {
40 /* FUNCTION init */
41 int i;
42 int j;
43 int k;
44 int m;
45 unsigned int t1;
46 unsigned int t2;
47 unsigned int t3;
48 unsigned int t4;
49
50 numPrimes = 1;
51 primes[1] = 2;
52
53 /* sieve of erasthones */
54 for (i=3; i<MAX_NUM; i=i+2)
55 {
56 flags[i][0]=1;
57 flags[i+1][0]=0;
58 }
59 for (i=3; i<MAX_NUM; i=i+2)
60 {
61 /* loop through primes */
62 if (0 != flags[i][0])
63 {
64 /* found a prime */
65 numPrimes++;
66 primes[numPrimes] = i;
67 DEBUG printf("primes[%d] = %d\n", numPrimes, primes[numPrimes]);
68 for (j=i; j<MAX_NUM; j=j+i+i)
69 {
70 /* mark out multiples */
71 flags[j][0] = 0;
72 } /* mark out multiples */
73 } /* found a prime */
74 } /* loop through primes */
75 printf("numPrimes=%d (%d)\n", numPrimes, primes[numPrimes]);
76
77 /* now form all possible sums */
78 for (i=1; (numPrimes-2)>i; i++)
79 {
80 /* for each possible first prime */
81 t1 = primes[i];
82 DEBUG printf(" (i %d) (t1 %d)\n", i, t1);
83 for (j=i; (numPrimes-1)>j; j++)
84 {
85 /* for second possible addend */
86 t2 = primes[j] + t1;
87 for (k=j; (numPrimes)>k; k++)
88 {
89 /* for third possible addend */
90 t3 = primes[k] + t2;
91 for (m=k; ((MAX_NUM - primes[m]) >= t3) && (numPrimes>=m); m++)
92 {
93 /* for fourth possible addend */
94 t4 = t3 + primes[m];
95 if (0 == flags[t4][0])
96 {
97 /* not found before */
98 flags[t4][0] = primes[i];
99 flags[t4][1] = primes[j];
100 flags[t4][2] = primes[k];
101 flags[t4][3] = primes[m];
102 printf("%d = %d(%d) %d(%d) %d(%d) %d(%d)\n", t4, flags[t4][0], i, flags[t4][1], j, flags[t4][2], k, flags[t4][3], m);
103 } /* not found before */
104 else
105 printf("%d * %d %d %d %d (%d %d %d %d)\n", t4, flags[t4][0], flags[t4][1], flags[t4][2], flags[t4][3], primes[i], primes[j], primes[k], primes[m]);
106 } /* for fourth possible addend */
107 } /* for third possible addend */
108 } /* for second possible addend */
109 } /* for each possible first prime */
110 } /* FUNCTION init */
111
112 void dump()
113 {
114 /* FUNCTION dump */
115 } /* FUNCTION dump */
116
117 int getInput()
118 {
119 /* FUNCTION getInput */
120 int dataReadFlag;
121
122 fgets(line, MAX_LINE, stdin);
123 if (feof(stdin))
124 dataReadFlag = FALSE;
125 else
126 {
127 /* something to read */
128 dataReadFlag = TRUE;
129 line[strlen(line)-1] = 0;
130 sscanf(line, " %d ", &num);
131 } /* something to read */
132 return (dataReadFlag);
133 } /* FUNCTION getInput */
134
135 void process()
136 {
137 /* FUNCTION process */
138 if (0 == flags[num][0])
139 {
140 /* impossible */
141 printf("Impossible.\n");
142 } /* impossible */
143 else
144 {
145 /* print out 4 values */
146 printf("%d %d %d %d\n", flags[num][0], flags[num][1], flags[num][2], flags[num][3]);
147 } /* print out 4 values */
148 } /* FUNCTION process */
149
150 int main()
151 {
152 /* main */
153 int moreToDo;
154
155 init();
156 moreToDo = getInput();
157 while (moreToDo)
158 {
159 /* while */
160 process();
161 moreToDo = getInput();
162 } /* while */
163
164 return EXIT_SUCCESS;
165 } /* main */
166