/home/toolbox/public_html/solutions/106/10699/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 #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++)
81 {
82 if (0 == buff[j])
83 {
84 cnt++;
85 }
86 }
87 DEBUG printf("saved: %d\n", cnt);
88
89 buff[1] = 0;
90 for (i=2; i<MAX_SIZE; i++)
91 {
92 /* test all the numbers */
93 if (0 == buff[i])
94 {
95 /* count factors */
96 t = i;
97 k = 1;
98 while (1 < t)
99 {
100 /* still another factor */
101 j = primes[k];
102 DEBUG printf("start %6d %6d %6d\n", i, t, j);
103 if (0 == (t % j))
104 {
105 buff[i]++;
106 }
107 while (0 == (t % j))
108 {
109 t = t / j;
110 }
111 if (0 != buff[t])
112 {
113 /* we have reduced the number to an already defined answer */
114 DEBUG printf("Lookup success: %d %d\n", i, t);
115 buff[i] = buff[i] + buff[t];
116 t = 1;
117 } /* we have reduced the number to an already defined answer */
118 DEBUG printf("t=%d j=%d\n", t, j);
119 k++;
120 } /* still another factor */
121 } /* count factors */
122 } /* test all the numbers */
123 for (j=2; j<MAX_SIZE; j++) if (0 == buff[j]) cnt++;
124 cnt=0;
125 DEBUG printf("left: %d\n", cnt);
126
127 } /* FUNCTION init */
128
129 int dump()
130 {
131 /* FUNCTION dump */
132 int i;
133 for (i=1; i<=numPrimes; i++)
134 {
135 /*dump each prime */
136 printf("%4d:%5d\n", i, primes[i]);
137 } /*dump each prime */
138 printf("\nNumber of primes: %d\n\n", numPrimes);
139 } /* FUNCTION dump */
140
141 int getInput()
142 {
143 /* FUNCTION getInput */
144 int dataReadFlag;
145
146 scanf(" %d ", &num);
147
148 dataReadFlag = (0 != num);
149 return (dataReadFlag);
150 } /* FUNCTION getInput */
151
152 void process()
153 {
154 /* FUNCTION process */
155 printf("%d : %d\n", num, buff[num]);
156 } /* FUNCTION process */
157
158 int main ()
159 {
160 /* main */
161 int moreToDo;
162
163 init();
164 moreToDo = getInput();
165 while (moreToDo)
166 {
167 /* while */
168 process();
169 moreToDo = getInput();
170 } /* while */
171
172 return EXIT_SUCCESS;
173 } /* main */
174