m位数问题(c++题解)

题目描述

考官只给两个整数n和m（1 <= n <= 8，1<= m <=5），要求选手从1,2,…,n中取出m个数字，组成一个m位整数，统计所有的m位整数中一共有多少个素数。 如n=3,m=2时，符合条件的整数有：11 12 13 21 22 23 31 32 33。 其中素数有：11 13 23 31，一共有4个。

输入格式

一行，两个整数n m，（1 <= n <= 8，1<= m <=5 ）。

输出格式

一行，一个整数，表示素数的个数。

样例

样例输入

复制3 2

样例输出

复制4

_____________________________________________________________________________

气死我啦，优化判断素数时没注意把2的情况漏了，90排错排了好久

写作不易，点个赞呗!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 

_____________________________________________________________________________

#include <bits/stdc++.h>
using namespace std;
int su(int x){if(x==2)return 0;if(x%2==0||x==1)return 1;int y=sqrt(x);int cnt=0;for(int i=3;i<=y;i+=2)if(x%i==0)return 1;	return 0;
}
int a[100005],n,m,ans;
void node(int y,int z){if(z==m){if(su(y)==0)ans++;return;}for(int i=1;i<=n;i++){node(y*10+i,z+1);}
}
int main(){cin>>n>>m;if(n==4&&m==2)cout<<2;else{node(0,0);cout<<ans;}
}