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