/* 算法思想 暴力枚举（70分） 可以通过线性筛素数法将所有不超过n的素数求出， 然后枚举每个素数，判断是否符合超级素数的性质。 时间复杂度 O(10^8)，最终70分，TLE。 DFS 分析超级素数的性质，会发现最高位只能由素数2 、 3 、 5 、 7组成， 其余各位只能从是奇数1 、 3 、 7 、 9 中选择， 因此可以使用DFS构造所有满足性质的超级素数。 */ #include <iostream> #include <cmath> using namespace std; int ans,n; int a[]={2,3,5,7};//最高位 int b[]={1,3,7,9};//其他位 bool check(int x){//判断素数 if(x==1) return false; for(int i=2;i<=sqrt(x);i++) if(x%i==0) return false; return true; } void dfs(int x){//深搜 if(x>n) return; ans++; for(int i=0;i<4;i++) if(check(x*10+b[i])) dfs(x*10+b[i]); } int main() { cin>>n; for(int i=0;i<4;i++) dfs(a[i]); cout<<ans<<endl; return 0; }