/home/toolbox/public_html/solutions/105/10533/d2.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 2
34
35 int numberOfTimes;
36 int strt;
37 int stp;
38 int primes[MAX_SIZE];
39 int tot;
40
41 int xlate[3] = { 0, 0, 1 };
42
43 int digitPrime(int x)
44 {
45 /* FUNCTION digitPrime */
46 int tot = 0;
47
48 while (0 < x)
49 {
50 /* while */
51 tot = tot + (x % 10);
52 x = x / 10;
53 } /* while */
54 return (0 != primes[tot]);
55 } /* FUNCTION digitPrime */
56
57 void init()
58 {
59 /* FUNCTION init */
60 int i;
61 int j;
62
63 primes[0] = COMPOSITE;
64 primes[1] = COMPOSITE;
65 primes[2] = DIGITPRIME;
66
67 /* when done:
68 * composite numbers will be 0
69 * digit prime numbers will be -1
70 * prime numbers will be 1
71 */
72 /* sieve of erasthones (odds only) */
73 for (i=3,j=4; MAX_SIZE>i; i=i+2,j=j+2)
74 {
75 /* set odds to value and evens to 0 */
76 primes[i] = PRIME;
77 primes[j] = COMPOSITE;
78 } /* set odds to value and evens to 0 */
79 for (i=3; MAX_SIZE>i; i=i+2)
80 {
81 /* loop through primes */
82 if (COMPOSITE != primes[i])
83 {
84 /* found a prime */
85 for (j=i+i; MAX_SIZE>j; j=j+i)
86 {
87 /* mark out multiples */
88 primes[j] = COMPOSITE;
89 } /* mark out multiples */
90 } /* found a prime */
91 } /* loop through primes */
92 /* find digit primes */
93 for (i=3; MAX_SIZE>i; i=i+2)
94 {
95 /* for each prime */
96 if ((PRIME == primes[i]) && (digitPrime(i)))
97 {
98 primes[i] = DIGITPRIME;
99 }
100 } /* for each prime */
101 /* get count of inputs */
102 scanf("%d ", &numberOfTimes);
103 } /* FUNCTION init */
104
105 void dump()
106 {
107 /* FUNCTION dump */
108 } /* FUNCTION dump */
109
110 void getInput()
111 {
112 /* FUNCTION getInput */
113 scanf(" %d %d ", &strt, &stp);
114 } /* FUNCTION getInput */
115
116 void process()
117 {
118 /* FUNCTION process */
119 int i;
120
121 tot = 0;
122 if (3 > strt)
123 {
124 /* include 2 */
125 tot = 1;
126 strt = 3;
127 } /* include 2 */
128 /* make sure strt is odd */
129 strt = strt | 1;
130 for (i=strt; stp>i; i=i+2)
131 {
132 /* for - only check odds because evens will never be digitPrime */
133 tot = tot + xlate[primes[i]];
134 } /* for - only check odds because evens will never be digitPrime */
135 } /* FUNCTION process */
136
137 int main()
138 {
139 /* main */
140 int i;
141 struct timeval t0;
142 struct timeval t1;
143 int tmp;
144
145 gettimeofday(&t0, 0);
146 init();
147 gettimeofday(&t1, 0);
148 tmp= ((t1.tv_sec - t0.tv_sec) * 1000) + t1.tv_usec - t0.tv_usec;
149 printf("init: %d\n", tmp);
150 for (i=0; i<numberOfTimes; i++)
151 {
152 /* while */
153 gettimeofday(&t0, 0);
154 getInput();
155 gettimeofday(&t1, 0);
156 tmp= ((t1.tv_sec - t0.tv_sec) * 1000) + t1.tv_usec - t0.tv_usec;
157 printf("getInput: %d\n", tmp);
158 gettimeofday(&t0, 0);
159 process();
160 gettimeofday(&t1, 0);
161 tmp= ((t1.tv_sec - t0.tv_sec) * 1000) + t1.tv_usec - t0.tv_usec;
162 printf("process: %d\n", tmp);
163 printf("%d\n", tot);
164 } /* while */
165
166 return EXIT_SUCCESS;
167 } /* main */
168
169