/home/toolbox/public_html/solutions/2/294/d.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 int factor(int num)
46 {
47 /* FUNCTION factor */
48 int tmp;
49 int i = 0;
50 int tot = 1;
51 int ptot;
52
53 if (1 == num)
54 {
55 tot = 1;
56 }
57 else
58 {
59 /* work to do */
60 tmp = num;
61 while (1 < tmp)
62 {
63 /* while */
64 ptot = 1;
65 while (0 == (tmp % primes[i]))
66 {
67 /* divisor found */
68 tmp = tmp / primes[i];
69 ptot++;
70 } /* divisor found */
71 if (1 < ptot)
72 {
73 tot = tot * ptot;
74 }
75 i++;
76 if ((1 < tmp) && ((primes[i] * primes[i]) > num))
77 {
78 tmp = 1; /* only check numbers less than square root */
79 tot = tot * 2;
80 }
81 } /* while */
82 } /* work to do */
83 return tot;
84 } /* FUNCTION factor */
85
86 void init()
87 {
88 /* FUNCTION init */
89 int i;
90 int j;
91
92 primes[0] = 2;
93 primeCnt = 1;
94
95 /* sieve of erasthones */
96 for (i=0,j=3; i<MAX_SIZE; i++,j=j+2)
97 {
98 buff[i]=j;
99 }
100 for (i=0; (MAX_PRIMES>primeCnt)&&(MAX_SIZE>i); i++)
101 {
102 /* loop through primes */
103 if (0 != buff[i])
104 {
105 /* found a prime */
106 DEBUG printf("%d -- buff[%d] = %d\n", primeCnt, i, buff[i]);
107 primes[primeCnt++] = buff[i];
108 for (j=i+buff[i]; j<MAX_SIZE; j=j+buff[i])
109 {
110 /* mark out multiples */
111 buff[j] = 0;
112 } /* mark out multiples */
113 buff[i] = 0;
114 } /* found a prime */
115 } /* loop through primes */
116 DEBUG printf("pime cnt %d\n", primeCnt);
117 for (i=1; i<MAX_BUFFER; i++)
118 {
119 buff[i] = factor(i);
120 }
121 scanf(" %d ", &numberOfTimes);
122 } /* FUNCTION init */
123
124 void dump()
125 {
126 /* FUNCTION dump */
127 } /* FUNCTION dump */
128
129 void getInput()
130 {
131 /* FUNCTION getInput */
132 scanf(" %d %d ", &L, &U);
133 } /* FUNCTION getInput */
134
135 void process()
136 {
137 /* FUNCTION process */
138 int i;
139 int mx = 0;
140 int save;
141
142 DEBUG printf("Between %d and %d\n", L, U);
143 for (i=L; i<=U; i++)
144 {
145 /* proces each possible number */
146 if (buff[i] > mx)
147 {
148 mx = buff[i];
149 save = i;
150 }
151 } /* proces each possible number */
152 printf("Between %d and %d, %d has a maximum of %d divisors.\n", L, U, save, mx);
153 } /* FUNCTION process */
154
155 int main()
156 {
157 /* main */
158 int i;
159
160 init();
161 for (i=0; i<numberOfTimes; i++)
162 {
163 /* for */
164 getInput();
165 process();
166 } /* for */
167
168 return EXIT_SUCCESS;
169 } /* main */
170