超级素数
程序名：super.cpp super.in super.out
题目描述：
一个素数，依次从低位去掉一位，二位，……，若所得的各数仍都是素数，则称超级素数。
例如：7331是个4位超级素数，因为7，73，733，7331均为素数. 试求n位数的超级素数： (1)超级素数的个数 (2)所有超级素数之和 (3)最大的超级素数。
输入描述：
输入一个整数n(n<=10)
输出描述：
输出三个整数，分别为超级素数的个数，所有超级素数之和，最大的超级素数； 无解输出-1
样式输入：
4
样式输出：
16
68910
7393
刚看到数据规模约定：1010！！无论是埃拉托斯特尼筛法(O(NloglogN))，还是线性筛法(O(N))，都无法筛出那么多质数用来判断。
然后我很天真的 想把质数筛出来，粘贴到程序里。
然后就产生了几十万行代码：
蛤，无法编译。
再想，发现自己一直在避免试除法(O(sqrt(n)))，原因就是它太疯狂了。最坏情况下，1010要试除105次，宽搜1、3、7、9四个数一共有九层，49大概是105，不包括已经筛掉的合数肯定会超时。
那如果包括呢？？？
试一试就知道了。瞬间出答案。竟然如此简单！
1 #include
2 #include
3 using namespace std;
4
5 long long data[100000], x;
6 int d[5] = {0, 1, 3, 7, 9};
7 int n, op=0, cl=4, start=1;
8 int ans, sum;
9 bool is_prime(int x){
10 for(int i=2; i*i<=x; i++)
11 if(x % i == 0) return 0;
12 return 1;
13 }
14 int bit(long long x){
15 int ans = 0;
16 while(x){
17 x /= 10;
18 ans++;
19 }
20 return ans;
21 }
22 int main(){
23 cin >> n;
24 //特判
25 if(n > 9){
26 cout << -1 <<"\n";
27 return 0;
28 }
29 data[1] = 2;
30 data[2] = 3;
31 data[3] = 5;
32 data[4] = 7;
33 while(op < cl){
34 op++;
35 for(int i=1; i<=4; i++){
36 x = data[op] * 10 + d[i];
37 if(is_prime(x)){
38 cl++;
39 data[cl] = x;
40 }
41 }
42 }
43
44 // find the start position
45 while(bit(data[start]) < n)
46 start++;
47
48 while(bit(data[start]) == n){
49 ans++;
50 sum += data[start];
51 start++;
52 }
53
54 cout << ans <<"\n"<< sum <<"\n"<< data[start-1] <<"\n";
55 return 0;
56 }