/home/toolbox/public_html/solutions/106/10699/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
10 #define TRUE (1 == 1)
11 #define FALSE (1 != 1)
12
13 #define DEBUG if (FALSE)
14
15 #define MAX_PRIMES 78505
16 #define MAX_SIZE 1000005
17
18 /*
19 * Author:
20 * Date: 2005-07-20
21 * Purpose: practice
22 * Problem: 10699
23 */
24
25 /*
26 * This template reads data until a terminating value is reached.
27 */
28
29 int num;
30 int primes[MAX_PRIMES];
31 int buff[MAX_SIZE];
32 int numPrimes;
33
34 int init()
35 {
36 /* FUNCTION init */
37 int i;
38 int j;
39 int k;
40 int cnt;
41 int t;
42
43 numPrimes = 1;
44 primes[1] = 2;
45
46 /* sieve of erasthones */
47 for (i=3; i<MAX_SIZE; i=i+2) buff[i]=i;
48 for (i=3; i<MAX_SIZE; i=i+2)
49 {
50 /* loop through primes */
51 if (0 != buff[i])
52 {
53 /* found a prime */
54 numPrimes++;
55 primes[numPrimes] = i;
56 for (j=i; j<MAX_SIZE; j=j+i+i)
57 {
58 /* mark out multiples */
59 buff[j] = 0;
60 } /* mark out multiples */
61 } /* found a prime */
62 } /* loop through primes */
63
64 /* empty the buffer */
65 for (i=2; i<MAX_SIZE; i=i+1) buff[i]=0;
66
67 /* fill in the primes */
68 for (i=1; i<=numPrimes; i++)
69 {
70 /* do the easy parts */
71 t = primes[i];
72 buff[t] = 1;
73 for (j=t*t; (j<MAX_SIZE) && (0 < j); j=j*t)
74 {
75 /* remove powers of the prime number */
76 buff[j] = 1;
77 } /* remove powers of the prime number */
78 } /* do the easy parts */
79 cnt = 0;
80 for (j=2; j<MAX_SIZE; j++) if (0 == buff[j]) cnt++;
81 printf("saved: %d\n", cnt);
82
83 buff[1] = 0;
84 for (i=2; i<MAX_SIZE; i++)
85 {
86 /* test all the numbers */
87 if (0 == buff[i])
88 {
89 /* count factors */
90 t = i;
91 k = 1;
92 while (1 < t)
93 {
94 /* still another factor */
95 j = primes[k];
96 DEBUG printf("start %6d %6d %6d\n", i, t, j);
97 if (0 == (t % j))
98 {
99 buff[i]++;
100 }
101 while (0 == (t % j))
102 {
103 t = t / j;
104 }
105 if (0 != buff[t])
106 {
107 /* we have reduced the number to an already defined answer */
108 DEBUG printf("Lookup success: %d %d\n", i, t);
109 buff[i] = buff[i] + buff[t];
110 t = 1;
111 } /* we have reduced the number to an already defined answer */
112 DEBUG printf("t=%d j=%d\n", t, j);
113 k++;
114 } /* still another factor */
115 } /* count factors */
116 } /* test all the numbers */
117 printf("buff[1]=0;");
118 for (j=2; j<MAX_SIZE; j++)
119 {
120 if (0 == buff[j]) cnt++;
121 printf("buf[%d]=%d;\n", j, buff[j]);
122 }
123 cnt=0;
124 printf("left: %d\n", cnt);
125
126 } /* FUNCTION init */
127
128 int dump()
129 {
130 /* FUNCTION dump */
131 int i;
132 for (i=1; i<=numPrimes; i++)
133 {
134 /*dump each prime */
135 printf("%4d:%5d\n", i, primes[i]);
136 } /*dump each prime */
137 printf("\nNumber of primes: %d\n\n", numPrimes);
138 } /* FUNCTION dump */
139
140 int getInput()
141 {
142 /* FUNCTION getInput */
143 int dataReadFlag;
144
145
146 dataReadFlag = (0 != 0);
147 return (dataReadFlag);
148 } /* FUNCTION getInput */
149
150 void process()
151 {
152 /* FUNCTION process */
153 } /* FUNCTION process */
154
155 int main ()
156 {
157 /* main */
158 int moreToDo;
159
160 init();
161 // dump();
162 moreToDo = getInput();
163 while (moreToDo)
164 {
165 /* while */
166 process();
167 moreToDo = getInput();
168 } /* while */
169
170 return EXIT_SUCCESS;
171 } /* main */
172