蓝桥杯算法提高VIP-特殊的质数肋骨-题解（C++代码）最优解还是看这个吧

解题思路:
        从简单的来看，比如只有一位，那么必然只有 2，3，5，7

        再看两位，由题目要求，该两位数必为质数，且丢弃个位后，仍为质数。

        那么反过来看，从一位到两位，有什么规律呢？

        核心：以一位 5 为例，欲扩展到两位，最多只要判断 51，53，57，59 即可，也就是 (5*10) + 1 / +3 / +7 / +9

        【个位为0，2，4，6，8一定不为质数，5也排除在外

        再继续看，以53为例，欲扩展至三位，最多只要判断 531，533，537，539 即可  也就是 (53*10) + 1 / +3 / +7 / +9

        所以规律已经显而易见了

        （如果采用暴力算法，例如N=3，去遍历100~999再判断的话，必然超时，再怎么优化细节也不可行（主要是N=8太久了）

注意事项:
        判断质数函数 用的不是最优算法，有兴趣的同学再去研究一下吧

参考代码:

#include<bits/stdc++.h>
using namespace std;

bool IsPrime(int num)
{
    if (num <= 3)  return num > 1;
    int s = sqrt(num);
    for (int i = 2; i <= s; ++i) {
        if (num % i == 0)   return false;
    }
    return true;
}

int main()
{
    int n;
    while (cin >> n) {
        // int型链表
        list<int> li;
        // 迭代器
        list<int>::iterator iter;
        int i, j, tmp;
        // 记录当前n所对应的特殊质数的个数，比如n=1时，count=4
        int count = 0;
        // 初始化为 2 3 5 7
        li.push_back(2);
        li.push_back(3);
        li.push_back(5);
        li.push_back(7);
        // 从n=1开始，扩展到题目要求的n
        for (i = 1; i < n; ++i) {
            // 更新count
            count = li.size();
            // 从list第一个数开始处理
            iter = li.begin();
            // 一共处理count个数
            while (count != 0) {
                // 优化效率，防止多次运算
                tmp = (*iter) * 10;
                // 取完数后，指针指向下一个待处理的数
                iter++;
                // 删除已记录在tmp的那个数
                li.pop_front();    
                // 更新count    
                count--;
                // 对应的 +1 +3 +7 +9，想写循环的话：tmp += 2，但是这样写更直观
                if (IsPrime(tmp + 1)) {
                    li.push_back(tmp + 1);
                }
                if (IsPrime(tmp + 3)) {
                    li.push_back(tmp + 3);
                }
                if (IsPrime(tmp + 7)) {
                    li.push_back(tmp + 7);
                }
                if (IsPrime(tmp + 9)) {
                    li.push_back(tmp + 9);
                }
                
            }
        }
        // 输出即可
        for (iter = li.begin(); iter != li.end(); ++iter) {
            cout << (*iter) << endl;
        }    
    }
    return 0;
}

解题思路:
        嫌上面麻烦的同学，这里有一份更直接的AC代码
注意事项:
        定向输出！
参考代码:

#include<bits/stdc++.h>
using namespace std;

void outputArr(int A[], int size)
{
    for (int i = 0; i < size; ++i) {
        cout << A[i] << endl;
    }
}

int main()
{
    int n;
    while (cin >> n) {
        
        int N1[] = { 2,3,5,7 };
        int N2[] = { 23,29,31,37,53,59,71,73,79 };
        int N3[] = { 233,239,293,311,313,317,373,379,593,599,719,733,739,797 };
        int N4[] = { 2333,2339,2393,2399,2939,3119,3137,3733,3739,3793,3797,5939,7193,7331,7333,7393 };
        int N5[] = { 23333,23339,23399,23993,29399,31193,31379,37337,37339,37397,59393,59399,71933,73331,73939 };
        int N6[] = { 233993,239933,293999,373379,373393,593933,593993,719333,739391,739393,739397,739399 };
        int N7[] = { 2339933,2399333,2939999,3733799,5939333,7393913,7393931,7393933 };
        int N8[] = { 23399339,29399999,37337999,59393339,73939133 };

        switch (n)
        {
        case 1: outputArr(N1, 4); break;
        case 2: outputArr(N2, 9); break;
        case 3: outputArr(N3, 14); break;
        case 4: outputArr(N4, 16); break;
        case 5: outputArr(N5, 15); break;
        case 6: outputArr(N6, 12); break;
        case 7: outputArr(N7, 8); break;
        case 8: outputArr(N8, 5); break;
        default:
            break;
        }
    }
    return 0;
}