/home/toolbox/public_html/solutions/4/412/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 #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 numPrimes = 1;
45 primeList[0] = 2;
46 primes[2] = 1;
47
48 /* sieve of erasthones */
49 for (i=0,j=3; i<MAX_SIZE; i++,j=j+2)
50 {
51 n[i]=j;
52 primes[i] = 0;
53 primes[i+MAX_SIZE] = 0;
54 }
55 for (i=0; i<MAX_SIZE; i++)
56 {
57 /* loop through primes */
58 if (0 != n[i])
59 {
60 /* found a prime */
61 numPrimes++;
62 primeList[numPrimes] = n[i];
63 primes[n[i]] = 1;
64 for (j=i+n[i]; j<MAX_SIZE; j=j+n[i])
65 {
66 /* mark out multiples */
67 n[j] = 0;
68 } /* mark out multiples */
69 } /* found a prime */
70 } /* loop through primes */
71 } /* FUNCTION init */
72
73 void dump()
74 {
75 /* FUNCTION dump */
76 int i;
77
78 for (i=0; i<cnt; i++)
79 {
80 printf("%2d: %d\n", i, n[i]);
81 }
82 } /* FUNCTION dump */
83
84 int getInput()
85 {
86 /* FUNCTION getInput */
87 int dataReadFlag;
88 int i;
89
90 scanf(" %d ", &cnt);
91 dataReadFlag = (0 < cnt);
92 if (dataReadFlag)
93 {
94 /* load up n */
95 for (i=0; i<cnt; i++)
96 {
97 /* for */
98 scanf(" %d ", &n[i]);
99 } /* for */
100 } /* load up n */
101 return (dataReadFlag);
102 } /* FUNCTION getInput */
103
104 int commonFactor(int a, int b)
105 {
106 /* FUNCTION commonFactor */
107 int mx;
108 int s;
109 int retFlag;
110 int i;
111
112 mx = (a > b) ? a : b;
113 s = (a < b) ? a : b;
114 printf("(s, %d) (mx, %d)\n", s, mx);
115 retFlag = (1 == s); /* one and anything have no common factors other than 1 */
116 if (! retFlag)
117 {
118 /* look further */
119 DEBUG printf("s is not 1\n");
120 retFlag = (s == mx) || (0 == (mx % s));
121 DEBUG printf("s != mx and mx is not a multiple of s\n");
122 if (! retFlag) /* different numbers that are not multiples of each other */
123 {
124 /* keep looking */
125 DEBUG printf("Start checking primes\n");
126 /*
127 for (i=0; (! retFlag) && (s >= (primeList[i]*primeList[i])); i++)
128 */
129 DEBUG printf("pr[0] = %d\n", primeList[0]);
130 for (i=0; (! retFlag) && (s <= primeList[i]); i++)
131 {
132 /* check for a prime factor */
133 DEBUG printf("(S, %d) (mx, %d) (prime[%d] %d)\n", s, mx, i, primeList[i]);
134 retFlag = (0 != (s % primeList[i])) || (0 != (mx % primeList[i]));
135 } /* check for a prime factor */
136 } /* keep looking */
137 } /* look further */
138 return retFlag;
139 } /* FUNCTION commonFactor */
140
141 void process()
142 {
143 /* FUNCTION process */
144 int i;
145 int j;
146 int tot;
147 double calc;
148
149 tot = 0;
150 for (i=0; i<(cnt-1); i++)
151 {
152 /* first number */
153 for (j=i+1; j<cnt; j++)
154 {
155 /* second number */
156 printf("Checking %d and %d\n", n[i], n[j]);
157 if (! commonFactor(n[i], n[j]))
158 {
159 tot++;
160 }
161 } /* second number */
162 } /* first number */
163 if (0 == tot)
164 {
165 /* no relatively prime pairs */
166 printf("No estimate for this data set.\n");
167 } /* no relatively prime pairs */
168 else
169 {
170 /* do the math */
171 calc = cnt;
172 calc = tot / calc;
173 printf("%.6lf\n", calc);
174 } /* do the math */
175 } /* FUNCTION process */
176
177 int main()
178 {
179 /* main */
180 int moreToDo;
181
182 init();
183 moreToDo = getInput();
184 while (moreToDo)
185 {
186 /* while */
187 process();
188 moreToDo = getInput();
189 } /* while */
190
191 return EXIT_SUCCESS;
192 } /* main */
193