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