[朝阳区小学组 2019] factorization

Luogu

IDLGB4266

Time1000ms

Memory512MB

DifficultyP2

2019北京素数判断,质数,筛法科创活动小学活动

Adleman 非常喜欢数学，最近他遇到了一个棘手的问题：对于一个正整数 $A$，Adleman 发现一些自然数的质因子分解式中没有大于 $A$ 的因子，这样的自然数非常的特殊。Adleman 想知道对于给定的正整数 $A$，一个区间 $[N, N+M]$ 内所有满足上述条件的自然数的个数。 ## Input $3$ 个用空格分开的整数 $N,M,A$。 ## Output 一个整数，表示对于给定的正整数 $A$，区间 $[N, N+M]$ 内特殊自然数的个数。 [samples] ## Background 数据为洛谷自造。 ## Note ### 样例解释 $[30, 40]$ 之间的数质因子分解式如下： - $30=2\times 3\times 5$ - $31=1\times 31$ - $32=2\times 2\times 2\times 2\times 2$ - $33=3\times 11$ - $34=2\times 17$ - $35=5\times 7$ - $36=2\times 2\times 3\times 3$ - $37=1\times 37$ - $38=2\times 19$ - $39=3\times 13$ - $40=2\times 2\times 2\times 5$ 其中 $30,32,36,40$ 的质因子分解式中没有大于 $5$ 的因子，所以一共有 $4$ 个。 ### 数据范围 - $50\%$ 的数据满足：$1\leq N,M,A\leq 5000$； - $100\%$ 的数据满足：$1\leq N,M,A≤50\,000$；

Samples

Input #1

30 10 5

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[朝阳区小学组 2019] factorization",
    "description": {
      "content": "Adleman 非常喜欢数学，最近他遇到了一个棘手的问题：对于一个正整数 $A$，Adleman 发现一些自然数的质因子分解式中没有大于 $A$ 的因子，这样的自然数非常的特殊。Adleman 想知道对于给定的正整数 $A$，一个区间 $[N, N+M]$ 内所有满足上述条件的自然数的个数。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4266"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Adleman 非常喜欢数学，最近他遇到了一个棘手的问题：对于一个正整数 $A$，Adleman 发现一些自然数的质因子分解式中没有大于 $A$ 的因子，这样的自然数非常的特殊。Adleman 想知道对于给定的正整数 $A$，一个区间 $[N, N+M]$ 内所有满足上述条件的自然数的个数。\n\n## Input\n\n$3$ 个用空格分开的整数 $N,M,A$。\n\n## Output\n\n一个整数，表示...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments