/home/toolbox/public_html/solutions/106/10699/ryan2.c
1 #include <stdio.h>
2
3 /* Ryan Rousseau */
4
5 #define MAX 1000001
6 /*highest prime is less than 300000*/
7 #define HIGHNUM 300005
8 /* almost 26000 primes less than 300000 */
9 #define MAXPRIMES 26000
10
11 int primeIndices[HIGHNUM] = {0};
12 int lookUp[MAX] = {0};
13 int primes[MAXPRIMES] = {0};
14 int p_count = 0;
15 int factorMe;
16
17 /* ugly sieve off of the top of my head */
18 void sieve(void)
19 {
20 int i, n;
21 int cur;
22 for (i = 2; i <= HIGHNUM; i++)
23 {
24 if (primeIndices[i] != -1)
25 {
26 cur = i;
27 primeIndices[cur] = 1;
28 primes[p_count] = cur;
29 p_count++;
30 n = 2;
31 while (n * cur < HIGHNUM)
32 {
33 primeIndices[n * cur] = -1;
34 n++;
35 }
36 }
37 }
38 }
39
40 int readInput(void)
41 {
42 scanf(" %d ", &factorMe);
43 return factorMe;
44 }
45
46 int main(void)
47 {
48 int i;
49 int answer;
50 int temp;
51 int keepGoing;
52 sieve();
53 /* printf("%d\n", p_count); */
54 while (readInput())
55 {
56 answer = 1;
57 temp = factorMe;
58 keepGoing = 1;
59 for (i = 0; keepGoing && i < p_count && primes[i] < temp/2; i++)
60 {
61 /*
62 * if primes[i] divides factorMe evenly
63 * add one to the number of factors
64 */
65 if (lookUp[temp] != 0)
66 {
67 answer += lookUp[temp];
68 keepGoing = 0;
69 }
70 else if (temp % primes[i] == 0)
71 {
72 answer++;
73 /*printf("made it here\n"); */
74 while (temp % primes[i] == 0) temp /= primes[i];
75 /* printf("made it here\n"); */
76 }
77 }
78 lookUp[factorMe] = answer;
79 printf("%d : %d\n", factorMe, answer);
80 }
81 return 0;
82 }
83