[海淀区入门组 2025] 素数和回文数

Luogu

IDLGB4463

Time1000ms

Memory512MB

DifficultyP3

2025北京素数判断,质数,筛法小学活动

圣诞节的联欢活动上，还有一个找数游戏。如果一个数是大于 $1$ 的正整数，且不能被除了自身和 $1$ 以外的任何正整数整除，那么它被称为**质数**。如果一个正整数的十进制表示中没有前导零，且从左到右和从右到左读起来是一样的，则称它为**回文数**。定义：$f(n)$ 表示不大于 $n$ 的质数的个数，$g(n)$ 表示不大于 $n$ 的回文数的个数。你的任务是，对于给定的系数 $A$（是一个分数，由分子和分母构成），找出最大的正整数 $n$，使得 $f(n) \leq A \cdot g(n)$。 ## Input 输入仅有一行，包含两个正整数 $p$ 和 $q$ （$p, q \leq 10^4, \frac{1}{42} \leq \frac{p}{q} \leq 42$）（由空格分隔），它们分别为系数 $A$ 的分子和分母的值（即 $A$ 的值为 $\frac{p}{q}$）。 ## Output 如果存在符合题目要求的，最大的正整数 $n$，则输出这个 $n$，否则输出 $0$。 [samples]

Samples

Input #1

1 1

Output #1

Input #2

1 42

Output #2

Input #3

6 4

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[海淀区入门组 2025] 素数和回文数",
    "description": {
      "content": "圣诞节的联欢活动上，还有一个找数游戏。 如果一个数是大于 $1$ 的正整数，且不能被除了自身和 $1$ 以外的任何正整数整除，那么它被称为**质数**。 如果一个正整数的十进制表示中没有前导零，且从左到右和从右到左读起来是一样的，则称它为**回文数**。 定义：$f(n)$ 表示不大于 $n$ 的质数的个数，$g(n)$ 表示不大于 $n$ 的回文数的个数。 你的任务是，对于给定的系数 $",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4463"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "圣诞节的联欢活动上，还有一个找数游戏。\n\n如果一个数是大于 $1$ 的正整数，且不能被除了自身和 $1$ 以外的任何正整数整除，那么它被称为**质数**。\n\n如果一个正整数的十进制表示中没有前导零，且从左到右和从右到左读起来是一样的，则称它为**回文数**。\n\n定义：$f(n)$ 表示不大于 $n$ 的质数的个数，$g(n)$ 表示不大于 $n$ 的回文数的个数。\n\n你的任务是，对于给定的系数 $...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments