蓝桥杯算法提高VIP-特殊的质数肋骨 （C++代码）（DFS 属于此题最优解法了吧）

解题思路:

        DFS  5 ms 通关。

参考代码:

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

int Len;
bool IsPrime(int num) {
	for (int i = 2; i <= sqrt(num); i++)
		if (num / i*i == num)
			return false;
	return true;
}

void DFS(int now, int nowLne) {
	if (now == 1) return;
	if (nowLne == Len) {
		printf("%d\n", now); return;
	}

	for (int num = 1; num <= 9; num++) {
		int tmp = now * 10 + num;
		if (IsPrime(tmp))
			DFS(tmp, nowLne + 1);
	}
}

int main() {
	cin >> Len; DFS(0, 0);
}