Digit Primes
A prime number is a positive number, which is divisible by exactly two different integers. A digit prime is a prime number whose sum of digits is also prime. For example the prime number 41 is a digit prime
because 4+1=5 and 5 is a prime number. 17 is not a digit prime because 1+7 = 8, and 8 is not a prime number. In this problem your job is to find out the number of digit primes
within a certain range less than 1000000.
Input
First line of the input file contains a single integer N (0<N<=500000) that indicates the total number of inputs. Each of the next N lines contains two integers t1 and t2 (0<t1<=t2<1000000).
Output
For each line of input except the first line produce one line of output containing a single integer that indicates the number of digit primes between t1 and t2 (inclusive).
Sample Input
| 310 2010 100100 10000 | 110576 |
题目类型：素数测试
算法分析：首先使用Euler筛将2至1000000之间的所有的素数筛出来，然后从小到大判断所有的素数val的位数字之和是否为素数，如果是则将OK[val] = 1，然后将OK构建成一个前缀表，之后对于每一个查询直接求相应数的前缀差即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
#include <iostream> #include <fstream> #include <sstream> #include <algorithm> #include <iomanip> #include <cstring> #include <cstdio> #include <cmath> #include <map> #include <string> #include <vector> #include <stack> #include <queue> #include <set> #include <list> #include <ctime> using namespace std; const int maxn = 1000000 + 66; bool prime[maxn]; int primelist[maxn], num, Ok[maxn]; void Judge (int val) { int sum = 0, temp = val; do { sum += temp % 10; temp /= 10; } while (temp); if (prime[sum]) Ok[val]++; } void PrePare () { memset (prime, true, sizeof (prime)); memset (Ok, 0, sizeof (Ok)); num = 0; int i; for (i = 2; i <= maxn; i++) { if (prime[i]) primelist[num++] = i; int j; for (j = 0; j < num; j++) { if (i * primelist[j] > maxn) break; prime[i*primelist[j]] = false; if (i % primelist[j] == 0) break; } } } int main() { // freopen ("aaa.txt", "r", stdin); PrePare (); for (int i = 0; i < num; i++) Judge (primelist[i]); for (int i = 2; i <= maxn; i++) Ok[i] += Ok[i-1]; int n; scanf ("%d", &n); int i; for (i = 0; i < n; i++) { int val_a, val_b; scanf ("%d%d", &val_a, &val_b); printf ("%d\n", Ok[val_b] - Ok[val_a-1]); } return 0; } |
- « 上一篇：uva10168
- uva1593：下一篇 »