[蓝桥杯青少年组省赛 2023] 质因数的个数

Luogu

IDLGB4272

Time1000ms

Memory512MB

DifficultyP3

2023素数判断,质数,筛法蓝桥杯青少年组

给定两个正整数 $N$ 和 $M(1\leq N\leq M\leq 10^7)$，统计 $N$ 到 $M$ 之间（含 $N$ 和 $M$）每个数所包含的质因数的个数，输出其中最大的个数。例如：当 $N=6,M=10$，$6$ 到 $10$ 之间： - $6$ 的质因数是 $2,3$，共有 $2$ 个； - $7$ 的质因数是 $7$，共有 $1$ 个； - $8$ 的质因数是 $2,2,2$，共有 $3$ 个； - $9$ 的质因数是 $3,3$，共有 $2$ 个； - $10$ 的质因数是 $2,5$，共有 $2$ 个； $6$ 到 $10$ 之间的数中质因数最多的是 $8$，质因数有 $3$ 个，故输出 $3$。 ## Input 输入两个正整数 $N$ 和 $M(1\leq N\leq M\leq 10^7)$，两个正整数之间用一个空格隔开。 ## Output 输出一个整数，表示质因数个数中的最大值。 [samples] ## Background - **因数**：又称为约数，如果整数 $a$ 除以整数 $b(b\neq 0)$ 的商正好是整数而没有余数，我们就说 $b$ 是 $a$ 的因数。 - **质数**：又称为素数，一个大于 $1$ 的自然数，除了 $1$ 和它自身外，不能被其他自然数整除的数叫做质数。$2$ 是最小的质数。 - **质因数**：如果一个数 $a$ 的因数 $b$ 同时也是质数，那么 $b$ 就是 $a$ 的一个质因数，例如：$8=2\times 2\times2$，$2$ 就是 $8$ 的质因数；$12=2\times 2\times 3$，$2$ 和 $3$ 就是 $12$ 的质因数。

Samples

Input #1

6 10

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[蓝桥杯青少年组省赛 2023] 质因数的个数",
    "description": {
      "content": "给定两个正整数 $N$ 和 $M(1\\leq N\\leq M\\leq 10^7)$，统计 $N$ 到 $M$ 之间（含 $N$ 和 $M$）每个数所包含的质因数的个数，输出其中最大的个数。 例如： 当 $N=6,M=10$，$6$ 到 $10$ 之间： - $6$ 的质因数是 $2,3$，共有 $2$ 个； - $7$ 的质因数是 $7$，共有 $1$ 个； - $8$ 的质因数是 $2,2,2",
      "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": "LGB4272"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定两个正整数 $N$ 和 $M(1\\leq N\\leq M\\leq 10^7)$，统计 $N$ 到 $M$ 之间（含 $N$ 和 $M$）每个数所包含的质因数的个数，输出其中最大的个数。\n\n例如：\n当 $N=6,M=10$，$6$ 到 $10$ 之间：\n- $6$ 的质因数是 $2,3$，共有 $2$ 个；\n- $7$ 的质因数是 $7$，共有 $1$ 个；\n- $8$ 的质因数是 $2,2,2...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments