蓝桥杯算法提高VIP-特殊的质数肋骨 （C++代码）我用的是打表打出来所有符合条件的，然后直接输出

解题思路:

我的思路是先自己打表，用线性筛素数来打出1-1亿的素数，然后找出符合条件的2-99999999的素数

把每一个n对应符合条件的素数找出来，然后输出就好了。

#define N 100000050
bool flag[N];//false表示素数，true表示合数
int prime[N];
int num;//素数个数，也充当下标
void getprime(int n){
 int i, j;
 for (i = 2; i <= n; i++){
  if (!flag[i]){
   prime[num++] = i;
  }
  for (j = 0; j < num&&i*prime[j] <= n; j++){
   flag[i*prime[j]] = true;//把当前筛得的素数与已经筛到prime素数数组里面的素数逐一相乘
   /*
   如：当已经筛得了2，3之后，下一个素数就是5(i==5)的时候，这个时候筛得5，因为flag[5]=false
   然后用5对2和3进行相乘
   把flag[5(i)*prime[j]] =true;
   也就是把flag[5*2] = true和 flag[3*5] = true和flag[5*5] = true;
   */

   if (i%prime[j] == 0)break;//这里是优化的地方； 
   /*这里是用来处理那些偶数合数的筛选的，像刚才筛完2和3后，把4，6，9都筛掉了

   当i==4的时候，4显然不是素数，因为被筛选2的时候把4给筛掉了，所以就不用存储4进入到素数数组
   但还是会执行for循环，进入for循环，把flag[4*prime[0]] =true,也就是flag[4*2]=true,flag[8]给筛掉，
   然后满足条件i%prime[j] == 0条件跳出循环，然后开始筛选5
   */
  }
 }
}

这就是素数筛1-1亿的素数，都存放在prime数组中

然后就是找符合条件的，看代码

/***********************************************************************************************************

else if (n == 3){
  for (int i = 200; i < 800; ){
   k = i, j = 1;
   while (k){
    a[j++] = k;
    k /= 10;
   }
   for (k = 1; k < j; k++){
    if (flag[a[k]] == true)break;
   }
   if (k == j){
    cout << i << endl;
   }
   if (i <= 400){
    i++;
    if (i == 400) i = 500;
   }
   else if (i >= 500 && i <= 600){
    i++;
    if (i == 600)i = 700;
   }
   else if (i >= 700 && i < 800)i++;
  }
 }

else if (n == 4){
  for (int i = 2000; i < 8000;){
   k = i, j = 1;
   while (k){
    a[j++] = k;
    k /= 10;
   }
   for (k = 1; k < j; k++){
    if (flag[a[k]] == true)break;
   }
   if (k == j){
    cout << i << endl;
   }
   if (i <= 4000){
    i++;
    if (i == 4000) i = 5000;
   }
   else if (i >= 5000 && i <= 6000){
    i++;
    if (i == 6000)i = 7000;
   }
   else if (i >= 7000 && i < 8000)i++;
  }
 }

//******************************************************************************************

只拿一部分代码出来，这是n==3和4的情况，剩下的n==2-8的情况无非就是在200，400，500，600，700，800这些数字后面加多一个零而已，虽然代码很笨拙，但是这种题型就是看输出的而已，我都把答案找出来了，只要按照相应的n值来输出答案而已，快速
注意事项:

参考代码:

int main(){

int n; cin >> n;
  if (n == 1){
   cout << 2 << endl << 3 << endl << 5 << endl << 7;
  }
  else if (n == 2){
   cout << "11\n13\n17\n19\n23\n29\n31\n37\n53\n59\n71\n73\n79\n";
  }
  else if (n == 3){
   cout << "233\n239\n293\n311\n313\n317\n373\n379\n593\n599\n719\n733\n739\n797";
  }
  else if (n == 4){
   cout << "2333\n2339\n2393\n2399\n2939\n3119\n3137\n3733\n3739\n3793\n3797\n5939\n7193\n7331\n7333\n7393";
  }
  else if (n == 5){
   cout << "23333\n23339\n23399\n23993\n29399\n31193\n31379\n37337\n37339\n37397\n59393\n59399\n71933\n73331\n73939";
  }
  else if (n == 6){
   cout << "233993\n239933\n293999\n373379\n373393\n593933\n593993\n719333\n739391\n739393\n739397\n739399";
  }
  else if (n == 7){
   cout << "2339933\n2399333\n2939999\n3733799\n5939333\n7393913\n7393931\n7393933";
  }
  else if (n == 8){
   cout << "23399339\n29399999\n37337999\n59393339\n73939133";
  }

return 0;

}