/home/toolbox/public_html/solutions/101/10168/c.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 * Goldbach's conjecture which states that:
23 * "Every even integer greater than two can be expressed as the sum of two primes".
24 *
25 * Smallest sum of 4 primes is 8 -- all others ignored
26 *
27 * So even inputs will be 2 2 followed by sum of 2 primes
28 *
29 * Odd inputs will be 2 3 followed by sum of 2 primes (odd input - 5 makes new goal
30 * even therfore 2 primes can be found to solve it)
31 */
32
33 /*
34 * This template reads lines of data at a time until end of file.
35 */
36
37 #define MAX_LINE 257
38 #define MAX_NUM 10000001
39 #define MAX_PRIMES 664581
40
41 char line[MAX_LINE];
42 int flags[MAX_NUM+3][2];
43 int primes[MAX_PRIMES];
44 int numPrimes;
45 int num;
46
47
48 void init()
49 {
50 /* FUNCTION init */
51 int i;
52 int j;
53 int k;
54 int m;
55 int t1;
56 int t2;
57
58 numPrimes = 1;
59 primes[1] = 2;
60
61 /* sieve of erasthones */
62 for (i=3; i<MAX_NUM; i=i+2)
63 {
64 flags[i][0]=1;
65 flags[i+1][0]=0;
66 }
67 for (i=3; i<MAX_NUM; i=i+2)
68 {
69 /* loop through primes */
70 if (0 != flags[i][0])
71 {
72 /* found a prime */
73 numPrimes++;
74 primes[numPrimes] = i;
75 DEBUG printf("primes[%d] = %d\n", numPrimes, primes[numPrimes]);
76 for (j=i; j<MAX_NUM; j=j+i+i)
77 {
78 /* mark out multiples */
79 flags[j][0] = 0;
80 } /* mark out multiples */
81 } /* found a prime */
82 } /* loop through primes */
83 printf("numPrimes=%d (%d)\n", numPrimes, primes[numPrimes]);
84
85 /* now form all possible sums */
86 for (i=1; numPrimes>i; i++)
87 {
88 /* for each possible first prime */
89 t1 = primes[i];
90 DEBUG printf(" (i %d) (t1 %d)\n", i, t1);
91 for (j=i; ((MAX_NUM - t1) >= primes[j]) && (numPrimes>j); j++)
92 {
93 /* for second possible addend */
94 t2 = primes[j] + t1;
95 if (0 == flags[t2][0])
96 {
97 /* not found before */
98 flags[t2][0] = primes[i];
99 flags[t2][1] = primes[j];
100 } /* not found before */
101 } /* for second possible addend */
102 } /* for each possible first prime */
103 } /* FUNCTION init */
104
105 void dump()
106 {
107 /* FUNCTION dump */
108 } /* FUNCTION dump */
109
110 int getInput()
111 {
112 /* FUNCTION getInput */
113 int dataReadFlag;
114
115 fgets(line, MAX_LINE, stdin);
116 if (feof(stdin))
117 dataReadFlag = FALSE;
118 else
119 {
120 /* something to read */
121 dataReadFlag = TRUE;
122 line[strlen(line)-1] = 0;
123 sscanf(line, " %d ", &num);
124 } /* something to read */
125 return (dataReadFlag);
126 } /* FUNCTION getInput */
127
128 void process()
129 {
130 /* FUNCTION process */
131 if (8 <= num)
132 {
133 /* impossible */
134 printf("Impossible.\n");
135 } /* impossible */
136 else if (0 == (num % 2))
137 {
138 /* even number */
139 printf("2 2 %d %d\n", flags[num-4][0], flags[num-4][1]);
140 } /* even number */
141 else
142 {
143 /* odd number */
144 printf("2 3 %d %d\n", flags[num-5][0], flags[num-5][1]);
145 } /* odd number */
146 } /* FUNCTION process */
147
148 int main()
149 {
150 /* main */
151 int moreToDo;
152
153 init();
154 moreToDo = getInput();
155 while (moreToDo)
156 {
157 /* while */
158 process();
159 moreToDo = getInput();
160 } /* while */
161
162 return EXIT_SUCCESS;
163 } /* main */
164