先预处理出来比小于等于n的素数的个数和回文数的个数…
素数不筛竟然也可以过
然后暴力就好.
需要注意的是，比值并不单调，找最大的n，可能之前某个数开始不满足条件，之后又有满足条件的了.
我们可以倒着扫来找，第一个满足条件的就是最大的.
代码实现
1/*************************************************************************
2 > File Name: code/cf/#315/C.cpp
3 > Author: 111qqz
4 > Email: rkz2013@126.com
5 > Created Time: 2015年08月11日 星期二 00时54分13秒
6 ************************************************************************/
7
8#include<iostream>
9#include<iomanip>
10#include<cstdio>
11#include<algorithm>
12#include<cmath>
13#include<cstring>
14#include<string>
15#include<map>
16#include<set>
17#include<queue>
18#include<vector>
19#include<stack>
20#define y0 abc111qqz
21#define y1 hust111qqz
22#define yn hez111qqz
23#define j1 cute111qqz
24#define tm crazy111qqz
25#define lr dying111qqz
26using namespace std;
27#define REP(i, n) for (int i=0;i<int(n);++i)
28typedef long long LL;
29typedef unsigned long long ULL;
30const int inf = 0x7fffffff;
31const int N=2E6+5;
32int f[N],g[N];
33bool prime( int x)
34{
35 if (x==1) return false;
36 if (x<=3) return true;
37 for ( int i = 2 ; i*i<=x ; i ++)
38 {
39 if (x%i==0)
40 return false;
41 }
42 return true;
43}
44bool pal( int x)
45{
46 int a[100];
47 int len=0;
48 while(x)
49 {
50 len++;
51 a[len]=x;
52 x = x/ 10;
53 }
54
55 for ( int i = 1 ;i <= len/2 ; i++)
56 {
57 if (a[i]!=a[len+1-i])
58 return false;
59 }
60 return true;
61}
62int main()
63{
64 int cnt = 0;
65 memset(f,0,sizeof(f));
66 memset(g,0,sizeof(g));
67 for (int i = 1 ; i <= N-5 ; i ++)
68 {
69 if (prime(i))
70 {
71 cnt++;
72
73 // pri[cnt] = i;
74 }
75 f[i] = cnt;
76 }
77 int cnt2 = 0 ;
78 for ( int i =1 ; i <=N-5 ; i++)
79 {
80 if (pal(i))
81 {
82 cnt2++;
83
84 }
85 g[i] = cnt2;
86 }
87 // for ( int i =1; i <= N-5; i ++)
88 // {
89// cout<<"i:"<<i<<"f[i]:"<<f[i]<<" g[i]:"<<g[i]<<"f[i]/g[i]:"<<f[i]*1.0/g[i]*1.0<<" g[i]/f[i]"<<g[i]*1.0/f[i]<<endl;
90 // }
91 int p,q;
92 int i = 0;
93 scanf("%d %d",&q,&p);
94 double r = p*1.0/q;
95 for ( int i = N-5 ; i >= 1 ; i--)
96 {
97 if (r*f[i]<=g[i])
98 {
99 cout<<i<<endl;
100 break;
101 }
102 }
103
104
105 return 0;
106}