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