/home/toolbox/public_html/solutions/106/10699/a1.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 for (j=2; j<MAX_SIZE; j++) if (0 == buff[j]) cnt++;
118 cnt=0;
119 printf("left: %d\n", cnt);
120
121 } /* FUNCTION init */
122
123 int dump()
124 {
125 /* FUNCTION dump */
126 int i;
127 for (i=1; i<=numPrimes; i++)
128 {
129 /*dump each prime */
130 printf("%4d:%5d\n", i, primes[i]);
131 } /*dump each prime */
132 printf("\nNumber of primes: %d\n\n", numPrimes);
133 } /* FUNCTION dump */
134
135 int getInput()
136 {
137 /* FUNCTION getInput */
138 int dataReadFlag;
139
140 scanf(" %d ", &num);
141
142 dataReadFlag = (0 != num);
143 return (dataReadFlag);
144 } /* FUNCTION getInput */
145
146 void process()
147 {
148 /* FUNCTION process */
149 printf("%6d : %d\n", num, buff[num]);
150 } /* FUNCTION process */
151
152 int main ()
153 {
154 /* main */
155 int moreToDo;
156
157 init();
158 // dump();
159 moreToDo = getInput();
160 while (moreToDo)
161 {
162 /* while */
163 process();
164 moreToDo = getInput();
165 } /* while */
166
167 return EXIT_SUCCESS;
168 } /* main */
169