/home/toolbox/public_html/solutions/101/10168/a.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 HALF_WAY 5000000
40 #define MAX_PRIMES 664581
41
42 char line[MAX_LINE];
43 int flags[MAX_NUM+3];
44 int primes[MAX_PRIMES];
45 int numPrimes;
46 int num;
47
48
49 void init()
50 {
51 /* FUNCTION init */
52 int i;
53 int j;
54 int k;
55 int m;
56 int t1;
57 int t2;
58
59 numPrimes = 1;
60 primes[1] = 2;
61
62 /* sieve of erasthones */
63 flags[2] = 1; /* set 2 */
64 for (i=3; i<MAX_NUM; i=i+2)
65 {
66 flags[i]=1;
67 flags[i+1]=0;
68 }
69 for (i=3; i<MAX_NUM; i=i+2)
70 {
71 /* loop through primes */
72 if (0 != flags[i])
73 {
74 /* found a prime */
75 numPrimes++;
76 primes[numPrimes] = i;
77 DEBUG printf("primes[%d] = %d\n", numPrimes, primes[numPrimes]);
78 for (j=i+i+i; j<MAX_NUM; j=j+i+i)
79 {
80 /* mark out multiples */
81 flags[j] = 0;
82 } /* mark out multiples */
83 } /* found a prime */
84 } /* loop through primes */
85 DEBUG printf("numPrimes=%d (%d)\n", numPrimes, primes[numPrimes]);
86 } /* FUNCTION init */
87
88 void dump()
89 {
90 /* FUNCTION dump */
91 } /* FUNCTION dump */
92
93 int getInput()
94 {
95 /* FUNCTION getInput */
96 int dataReadFlag;
97
98 fgets(line, MAX_LINE, stdin);
99 if (feof(stdin))
100 dataReadFlag = FALSE;
101 else
102 {
103 /* something to read */
104 dataReadFlag = TRUE;
105 line[strlen(line)-1] = 0;
106 sscanf(line, " %d ", &num);
107 } /* something to read */
108 return (dataReadFlag);
109 } /* FUNCTION getInput */
110
111 void findRest(int goal)
112 {
113 /* FUNCTION findRest */
114 int i;
115 int notFound = TRUE;
116
117 for (i=2; (notFound) && (HALF_WAY > i); i++)
118 {
119 /* look for pair of primes that add up to goal */
120 DEBUG printf("(goal %d) (flags[%d] %d) (flags[%d] %d)\n", goal, i, flags[i], goal-i, flags[goal-i]);
121 notFound = (0 == flags[i]) || (0 == flags[goal - i]);
122 } /* look for pair of primes that add up to goal */
123 i--;
124 printf("%d %d\n", i, goal -i);
125 } /* FUNCTION findRest */
126
127 void process()
128 {
129 /* FUNCTION process */
130 int rest;
131
132 if (8 > num)
133 {
134 /* impossible */
135 printf("Impossible.\n");
136 } /* impossible */
137 else
138 {
139 /* possible */
140 DEBUG printf("%d = ", num);
141 if (0 == (num % 2))
142 {
143 /* even number */
144 printf("2 2 ");
145 rest = num - 4;
146 } /* even number */
147 else
148 {
149 /* odd number */
150 printf("2 3 ");
151 rest = num - 5;
152 } /* odd number */
153 findRest(rest);
154 } /* possible */
155 } /* FUNCTION process */
156
157 int main()
158 {
159 /* main */
160 int moreToDo;
161
162 init();
163 moreToDo = getInput();
164 while (moreToDo)
165 {
166 /* while */
167 process();
168 moreToDo = getInput();
169 } /* while */
170
171 return EXIT_SUCCESS;
172 } /* main */
173