{"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一个整数，表示对于给定的正整数 $A$，区间 $[N, N+M]$ 内特殊自然数的个数。\n\n[samples]\n\n## Background\n\n数据为洛谷自造。\n\n## Note\n\n### 样例解释\n\n$[30, 40]$ 之间的数质因子分解式如下：\n- $30=2\\times 3\\times 5$\n- $31=1\\times 31$\n- $32=2\\times 2\\times 2\\times 2\\times 2$\n- $33=3\\times 11$\n- $34=2\\times 17$\n- $35=5\\times 7$\n- $36=2\\times 2\\times 3\\times 3$\n- $37=1\\times 37$\n- $38=2\\times 19$\n- $39=3\\times 13$\n- $40=2\\times 2\\times 2\\times 5$\n\n其中 $30,32,36,40$ 的质因子分解式中没有大于 $5$ 的因子，所以一共有 $4$ 个。\n\n### 数据范围\n\n- $50\\%$ 的数据满足：$1\\leq N,M,A\\leq 5000$；\n- $100\\%$ 的数据满足：$1\\leq N,M,A≤50\\,000$；","is_translate":false,"language":"English"}],"meta":{"iden":"LGB4266","tags":["2019","北京","素数判断,质数,筛法","科创活动","小学活动"],"sample_group":[["30 10 5","4"]],"created_at":"2026-03-03 11:09:25"}}