/home/toolbox/public_html/solutions/2/294/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
16
17 /*
18 * Author: Isaac Traxler
19 * Date: 2015-09-22
20 * Purpose: fun
21 * Problem: 294
22 */
23
24 /*
25 * This template reads data a counted number of times
26 */
27
28
29 #define MAX_PRIMES 6500
30 #define MAX_SIZE 32000
31 #define MAX_BUFFER 1000000001
32
33 /* buffer is used for:
34 1) buffer of raw numbers for sieve
35 2) cache any computed factor
36 */
37 unsigned short buff[MAX_BUFFER] = { 0 };
38 int primes[MAX_PRIMES];
39 int primeCnt;
40 int numberOfTimes;
41 int L;
42 int U;
43
44
45 void init()
46 {
47 /* FUNCTION init */
48 int i;
49 int j;
50
51 primes[0] = 2;
52 primeCnt = 1;
53
54 /* sieve of erasthones */
55 for (i=0,j=3; i<MAX_SIZE; i++,j=j+2)
56 {
57 buff[i]=j;
58 }
59 for (i=0; (MAX_PRIMES>primeCnt)&&(MAX_SIZE>i); i++)
60 {
61 /* loop through primes */
62 if (0 != buff[i])
63 {
64 /* found a prime */
65 DEBUG printf("%d -- buff[%d] = %d\n", primeCnt, i, buff[i]);
66 primes[primeCnt++] = buff[i];
67 for (j=i+buff[i]; j<MAX_SIZE; j=j+buff[i])
68 {
69 /* mark out multiples */
70 buff[j] = 0;
71 } /* mark out multiples */
72 buff[i] = 0;
73 } /* found a prime */
74 } /* loop through primes */
75 DEBUG printf("pime cnt %d\n", primeCnt);
76 scanf(" %d ", &numberOfTimes);
77 } /* FUNCTION init */
78
79 void dump()
80 {
81 /* FUNCTION dump */
82 } /* FUNCTION dump */
83
84 void getInput()
85 {
86 /* FUNCTION getInput */
87 scanf(" %d %d ", &L, &U);
88 } /* FUNCTION getInput */
89
90 int factor(int num)
91 {
92 /* FUNCTION factor */
93 int tmp;
94 int i = 0;
95 int tot = 1;
96 int ptot;
97
98 if (1 == num)
99 {
100 tot = 1;
101 }
102 else
103 {
104 /* work to do */
105 tmp = num;
106 while (1 < tmp)
107 {
108 /* while */
109 ptot = 1;
110 while (0 == (tmp % primes[i]))
111 {
112 /* divisor found */
113 tmp = tmp / primes[i];
114 ptot++;
115 } /* divisor found */
116 if (1 < ptot)
117 {
118 tot = tot * ptot;
119 }
120 i++;
121 if ((1 < tmp) && ((primes[i] * primes[i]) > num))
122 {
123 tmp = 1; /* only check numbers less than square root */
124 tot = tot * 2;
125 }
126 } /* while */
127 } /* work to do */
128 return tot;
129 } /* FUNCTION factor */
130
131 void process()
132 {
133 /* FUNCTION process */
134 int i;
135 int mx = 0;
136 int save;
137
138 DEBUG printf("Between %d and %d\n", L, U);
139 for (i=L; i<=U; i++)
140 {
141 /* proces each possible number */
142 if (0 == buff[i])
143 {
144 /* not cached */
145 DEBUG printf("factoring: %d ", i);
146 buff[i] = factor(i);
147 DEBUG printf(" factors = %d\n", buff[i]);
148 } /* not cached */
149 if (buff[i] > mx)
150 {
151 mx = buff[i];
152 save = i;
153 }
154 } /* proces each possible number */
155 printf("Between %d and %d, %d has a maximum of %d divisors.\n", L, U, save, mx);
156 } /* FUNCTION process */
157
158 int main()
159 {
160 /* main */
161 int i;
162
163 init();
164 for (i=0; i<numberOfTimes; i++)
165 {
166 /* for */
167 getInput();
168 process();
169 } /* for */
170
171 return EXIT_SUCCESS;
172 } /* main */
173