/home/toolbox/public_html/solutions/4/408/sieve.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 * Author: Isaac Traxler
17 * Date: 2018-08-28
18 * Purpose: fun
19 * Problem: 408 - Uniform Generator
20 */
21
22 /*
23 * This template reads data until a terminating value is reached.
24 */
25
26 #define MAX_PRIMES 10000
27 #define MAX_BUFFER 50003
28 #define MAX_SIZE (MAX_BUFFER * 2)
29
30 /* buffer is used for:
31 * 1) buffer of raw numbers for sieve
32 * */
33 unsigned short buff[MAX_BUFFER] = { 0 };
34 int primes[MAX_PRIMES];
35 int primeCnt;
36
37
38 int stp;
39 int md;
40
41 /* if stp and md are relatively prime, then they are good choices */
42
43 void init()
44 {
45 /* FUNCTION init */
46 int i;
47 int j;
48 int tmp;
49
50 primes[0] = 2;
51 primeCnt = 1;
52
53 /* sieve of erasthones */
54 for (i=0; (MAX_PRIMES>primeCnt)&&(MAX_BUFFER>i); i++)
55 {
56 /* loop through primes */
57 if (0 == buff[i])
58 {
59 /* found a prime */
60 tmp = (i * 2) + 3;
61 DEBUG printf("(%d) %d = %d\n", i, primeCnt, tmp);
62 primes[primeCnt++] = tmp;
63 for (j=i+tmp; j<MAX_BUFFER; j=j+tmp)
64 {
65 /* mark out multiples */
66 buff[j] = 1;
67 } /* mark out multiples */
68 } /* found a prime */
69 } /* loop through primes */
70 DEBUG printf("pime cnt %d\n", primeCnt);
71 } /* FUNCTION init */
72
73 void dump()
74 {
75 /* FUNCTION dump */
76 } /* FUNCTION dump */
77
78 int getInput()
79 {
80 /* FUNCTION getInput */
81 int dataReadFlag;
82
83 dataReadFlag = (2 == scanf(" %d %d ", &stp, &md));
84 return (dataReadFlag);
85 } /* FUNCTION getInput */
86
87 void process()
88 {
89 /* FUNCTION process */
90 int tmp;
91 int fnd = FALSE;
92 int i;
93
94 for (i=0; (primeCnt > i) && (primes[i] < stp) && (! fnd); i++)
95 {
96 /* is this prime a factor of both? */
97 fnd = ((0 == (stp % primes[i])) && (0 == (md % primes[i])));
98 } /* is this prime a factor of both? */
99
100 printf("%10d%10d ", stp, md);
101 if (fnd)
102 {
103 printf("Bad");
104 }
105 else
106 {
107 printf("Good");
108 }
109 printf(" Choice\n\n");
110
111 } /* FUNCTION process */
112
113 int main()
114 {
115 /* main */
116 int moreToDo;
117
118 init();
119 moreToDo = getInput();
120 while (moreToDo)
121 {
122 /* while */
123 process();
124 moreToDo = getInput();
125 } /* while */
126
127 return EXIT_SUCCESS;
128 } /* main */
129