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