/home/toolbox/public_html/solutions/105/10533/a-time.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 <stdlib.h>
7 #include <math.h>
8 #include <stdint.h>
9 #include <ctype.h>
10
11 #define TRUE (1 == 1)
12 #define FALSE (1 != 1)
13
14 #define DEBUG if (FALSE)
15
16 /* fprintf(stderr, "functionName: message", varslist); */
17
18 /*
19 * Author: Isaac Traxler
20 * Date: 10-19-2021
21 * Purpose: fun
22 * Problem: 10533 - Digit Primes
23 */
24
25 /*
26 * This template reads data a specified number of times.
27 */
28
29
30 #define MAX_SIZE 1000010
31 #define COMPOSITE 0
32 #define PRIME 1
33 #define DIGITPRIME 1
34
35 int numberOfTimes;
36 int strt;
37 int stp;
38 int primes[MAX_SIZE];
39 int tot;
40
41 int digitPrime(int x)
42 {
43 /* FUNCTION digitPrime */
44 int tot = 0;
45
46 while (0 < x)
47 {
48 /* while */
49 tot = tot + (x % 10);
50 x = x / 10;
51 } /* while */
52 return (0 != primes[tot]);
53 } /* FUNCTION digitPrime */
54
55 void init()
56 {
57 /* FUNCTION init */
58 int i;
59 int j;
60 int tot;
61
62 primes[0] = COMPOSITE;
63 primes[1] = COMPOSITE;
64 primes[2] = DIGITPRIME;
65
66 /* when done:
67 * composite numbers will be 0
68 * digit prime numbers will be -1
69 * prime numbers will be 1
70 */
71 /* sieve of erasthones (odds only) */
72 for (i=3,j=4; MAX_SIZE>i; i=i+2,j=j+2)
73 {
74 /* set odds to value and evens to 0 */
75 primes[i] = PRIME;
76 primes[j] = COMPOSITE;
77 } /* set odds to value and evens to 0 */
78 for (i=3; MAX_SIZE>i; i=i+2)
79 {
80 /* loop through primes */
81 if (COMPOSITE != primes[i])
82 {
83 /* found a prime */
84 for (j=i+i; MAX_SIZE>j; j=j+i)
85 {
86 /* mark out multiples */
87 primes[j] = COMPOSITE;
88 } /* mark out multiples */
89 } /* found a prime */
90 } /* loop through primes */
91 /* find digit primes */
92 for (i=(MAX_SIZE-1); 7<i; i=i-2)
93 {
94 /* for each prime */
95 if (PRIME == primes[i])
96 {
97 /* prime number found */
98 if (! digitPrime(i))
99 {
100 primes[i] = COMPOSITE;
101 }
102 } /* prime number found */
103 } /* for each prime */
104 /* now go through and sum up number of primes form 1 to n
105 * difference can then be found by primes[stop] - primes[start]
106 */
107 tot = 1;
108 for (i=3; MAX_SIZE>i; i++)
109 {
110 /* make each locaton a running sum */
111 tot = tot + primes[i];
112 primes[i] = tot;
113 } /* make each locaton a running sum */
114 /* get count of inputs */
115 scanf("%d ", &numberOfTimes);
116 } /* FUNCTION init */
117
118 void dump()
119 {
120 /* FUNCTION dump */
121 } /* FUNCTION dump */
122
123 void getInput()
124 {
125 /* FUNCTION getInput */
126 scanf(" %d %d ", &strt, &stp);
127 } /* FUNCTION getInput */
128
129 void process()
130 {
131 /* FUNCTION process */
132 printf("%d\n", (primes[stp] - primes[strt]));
133 } /* FUNCTION process */
134
135 int main()
136 {
137 /* main */
138 int i;
139 struct timeval t0;
140 struct timeval t1;
141 int tmp;
142
143 gettimeofday(&t0, 0);
144 init();
145 gettimeofday(&t1, 0);
146 tmp= ((t1.tv_sec - t0.tv_sec) * 1000) + t1.tv_usec - t0.tv_usec;
147 printf("init: %d\n", tmp);
148 for (i=0; i<numberOfTimes; i++)
149 {
150 /* while */
151 gettimeofday(&t0, 0);
152 getInput();
153 gettimeofday(&t1, 0);
154 tmp= ((t1.tv_sec - t0.tv_sec) * 1000) + t1.tv_usec - t0.tv_usec;
155 printf("getInput: %d\n", tmp);
156 gettimeofday(&t0, 0);
157 process();
158 gettimeofday(&t1, 0);
159 tmp= ((t1.tv_sec - t0.tv_sec) * 1000) + t1.tv_usec - t0.tv_usec;
160 printf("process: %d\n", tmp);
161 } /* while */
162
163 return EXIT_SUCCESS;
164 } /* main */
165
166