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