/home/toolbox/public_html/solutions/4/412/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 #include <ctype.h>
10
11 #define TRUE (1 == 1)
12 #define FALSE (1 != 1)
13
14 #define DEBUG if (FALSE)
15
16 /*
17 * Author: Isaac Traxler
18 * Date: 2021-02-05
19 * Purpose: fun
20 * Problem: 412 - Pi
21 */
22
23 /*
24 * This template reads data until a terminating value is reached.
25 */
26
27 #define MAX_NUMBERS 52
28 #define MAX_PRIMES 3550
29 #define MAX_SIZE 16384
30
31 int n[MAX_SIZE];
32 int cnt;
33 int primeList[MAX_PRIMES]; /* list of prime numbers */
34 int primes[MAX_SIZE*2]; /* bit array, if ith value is 1, then i is prime */
35 int numPrimes;
36
37
38 int init()
39 {
40 /* FUNCTION init */
41 int i;
42 int j;
43
44 /* sieve of erasthones */
45 for (i=0,j=3; i<MAX_SIZE; i++,j=j+2)
46 {
47 n[i]=j;
48 primes[i] = 0;
49 primes[i+MAX_SIZE] = 0;
50 }
51 primes[2] = 1;
52 numPrimes = 1;
53 primeList[0] = 2;
54 for (i=0; i<MAX_SIZE; i++)
55 {
56 /* loop through primes */
57 if (0 != n[i])
58 {
59 /* found a prime */
60 primeList[numPrimes] = n[i];
61 numPrimes++;
62 primes[n[i]] = 1;
63 for (j=i+n[i]; j<MAX_SIZE; j=j+n[i])
64 {
65 /* mark out multiples */
66 n[j] = 0;
67 } /* mark out multiples */
68 } /* found a prime */
69 } /* loop through primes */
70 } /* FUNCTION init */
71
72 void dump()
73 {
74 /* FUNCTION dump */
75 int i;
76
77 for (i=0; i<cnt; i++)
78 {
79 printf("%2d: %d\n", i, n[i]);
80 }
81 } /* FUNCTION dump */
82
83 int getInput()
84 {
85 /* FUNCTION getInput */
86 int dataReadFlag;
87 int i;
88
89 scanf(" %d ", &cnt);
90 dataReadFlag = (0 < cnt);
91 if (dataReadFlag)
92 {
93 /* load up n */
94 for (i=0; i<cnt; i++)
95 {
96 /* for */
97 scanf(" %d ", &n[i]);
98 } /* for */
99 } /* load up n */
100 return (dataReadFlag);
101 } /* FUNCTION getInput */
102
103 int commonFactor(int a, int b)
104 {
105 /* FUNCTION commonFactor */
106 int mx;
107 int s;
108 int retFlag;
109 int i;
110
111 mx = (a > b) ? a : b;
112 s = (a < b) ? a : b;
113 if (1 == s) /* one and anything have no common factors other than 1 */
114 {
115 /* s is 1 */
116 retFlag = FALSE;
117 DEBUG printf("s is 1\n");
118 } /* s is 1 */
119 else if (s == mx) /* numbers are same, so they do have a common factor */
120 {
121 /* numbers are same */
122 retFlag = TRUE;
123 DEBUG printf("s and mx are equal\n");
124 } /* numbers are same */
125 else if (0 == (mx % s))
126 {
127 /* mx is a multiple of s */
128 retFlag = TRUE;
129 DEBUG printf("mx is a multiple of s\n");
130 } /* mx is a multiple of s */
131 else
132 {
133 /* now look for a common prime divisor */
134 retFlag = FALSE;
135 for (i=0; (! retFlag) && (s >= primeList[i]); i++)
136 {
137 /* for */
138 DEBUG printf("(s %d) (mx %d) (primeList[%d] %d)\n", s, mx, i, primeList[i]);
139 retFlag = ((0 == (s % primeList[i])) && (0 == (mx % primeList[i])));
140 } /* for */
141 DEBUG if (retFlag)
142 {
143 printf("common factor\n");
144 }
145 else
146 {
147 printf("No common factor\n");
148 }
149 } /* now look for a common prime divisor */
150 return retFlag;
151 } /* FUNCTION commonFactor */
152
153 void process()
154 {
155 /* FUNCTION process */
156 int i;
157 int j;
158 int tot;
159 double calc;
160 int combos;
161
162 tot = 0;
163 combos = 0;
164 for (i=0; i<(cnt-1); i++)
165 {
166 /* first number */
167 for (j=i+1; j<cnt; j++)
168 {
169 /* second number */
170 combos++;
171 DEBUG printf("Checking %d and %d\n", n[i], n[j]);
172 if (! commonFactor(n[i], n[j]))
173 {
174 tot++;
175 }
176 } /* second number */
177 } /* first number */
178 if (0 == tot)
179 {
180 /* no relatively prime pairs */
181 printf("No estimate for this data set.\n");
182 } /* no relatively prime pairs */
183 else
184 {
185 /* do the math */
186 calc = 6 * combos;
187 calc = calc / tot;
188 DEBUG printf("(combos %d) / (tot %d) = (calc %lf)\n", combos, tot, calc);
189 calc = sqrt(calc);
190 printf("%.6lf\n", calc);
191 } /* do the math */
192 } /* FUNCTION process */
193
194 int main()
195 {
196 /* main */
197 int moreToDo;
198
199 init();
200 moreToDo = getInput();
201 while (moreToDo)
202 {
203 /* while */
204 process();
205 moreToDo = getInput();
206 } /* while */
207
208 return EXIT_SUCCESS;
209 } /* main */
210